0
$\begingroup$

I am trying to find an Algorithm to find the amount of elements in a BST which are greater than a certain number K.

I found it problematic as there are elements which might be greater then K but wont be found by traveling constantly to the right child, as there might be elements that are greater then K in the left sub-tree.

The Algorithm must be executed in a run-time complexity of O(h), while h is the height of the tree.

$\endgroup$
2
  • $\begingroup$ I suggest working through some examples. Take a look at an example and see what you could do about the problem you list. $\endgroup$
    – D.W.
    Commented Dec 10, 2020 at 20:39
  • $\begingroup$ The trick about useful trees is each node carrying information about its subtrees. In a BST, the key associated with a node is a limit for all keys both sub-trees. What would be helpful regarding amounts? $\endgroup$
    – greybeard
    Commented Dec 10, 2020 at 21:05

1 Answer 1

1
$\begingroup$

You can do it in $O(h)$ time only if you know some additional information at every node about the subtree rooted at that node. (Maybe @greybeard is suggesting the same in the comments). For example:

Suppose $x$ is any node in the tree, and suppose you know the number of nodes in the sub-tree rooted at $x$. Let us call this variable "x.total". Then, the following algorithm works in $O(h)$ time:

fun(root,K) // It returns the number of elements greter than K
---if (root = NULL)
------- return 0; 
---if(root.value > K)
-------- return fun(root.left_child,K) + 1 + root.right_child.total
---else
-------- return fun(root.right_child,K) 

The correctness of the above algorithm follows due to the fact that the given tree is a Binary Search tree (BST).

Moreover, you can maintain the extra information (i.e, x.total) for all nodes by traversing the tree only once. You can use DFS procedure for the same. Thus, the preprocessing time is only $O(n)$. And, the query time complexity would be just $O(h)$.


If you do not store any kind of extra information, then you can not do better than $O(n)$. For example: suppose the tree contains only positive elements and the query is for $K = 0$. Then, this query is the same as finding the total number of elements in the tree, which requires you to traverse every node and it essentially requires $\Omega(n)$ time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.