Would a balanced binary search tree help you complete the following task in a faster big-oh time than a balanced binary tree?
Creating a list of all elements in the tree that are smaller than some value v.
In my opinion no because what if all the values in the BST are smaller than v. Then you would have to visit each node and that would be O(n) which is not any better than a binary tree.
Am I correct?
In my opinion no because what if all the values in the BST are smaller than v. Then you would have to visit each node and that would be O(n) which is not any better than a binary tree.
Am I correct?
You are. Notice however that for all practical purposes is better to use BST, because with "plain" binary tree you always have to visit all nodes in order to find those smaller than v, while in BST with in-order traversal you examine only those smaller than v.
