BST, finding next highest node

Question

In BST, according to Programming Interviews Exposed

"Given a node, you can even find the next highest node in O(log(n)) time" Pg 65

A node in BST has right child as the next highest node, then why O(log(n))? Please correct

First answer the question, then negate it

Answer 1

With regard to your comment "A node in BST has right child as the next highest node" (assuming here "next highest" means the next sequential value) - no, it doesn't.

That can be the case if the right child has no left sub-tree, but it's not always so.

The next sequential value (I'm using that term rather than "highest" since the latter could be confused with tree height and "largest" implies a specific (low-to-high) order rather than any order) value comes from one of two places.

---

First, if the current node has a right child, move to that right child then, as long as you can see a left child, move to it.

In other words, with S and D as the source (current) and destination (next largest):

   S
  / \
 x   x <- This is the node your explanation chose,
    / \    but it's the wrong one in this case.
   x   x
  /
 D <----- This is the actual node you want.
  \
   x

---

Otherwise (i.e., if the current node has no right child), you need to move up to the parent continuously (so nodes need a right, left and parent pointer) until the node you moved from was a left child. If you get to the root and you still haven't moved up from a left child, your original node was already the highest in the tree.

Graphically that entire process is illustrated with:

x
 \
  D <- Walking up the tree until you came up
 / \     from a left node.
x   x
 \
  x
 / \
x   S
   /
  x

---

The pseudo-code for such a function (that covers both those cases) would be:

def getNextNode (node):
    # Case 1: right once then left many.

    if node.right != NULL:
        node = node.right
        while node.left != NULL:
            node = node.left
        return node

    # Case 2: up until we come from left.

    while node.parent != NULL:
        if node.parent.left == node:
            return node.parent
        node = node.parent

    # Case 3: we never came from left, no next node.

    return NULL

---

Since the effort is proportional to the height of the tree (we either go down, or up then down), a balanced tree will have a time complexity of O(log N) since the height has a logN relationship to the number of items.

The book is talking about balanced trees here, because it includes such snippets about them as:

• This lookup is a fast operation because you eliminate half the nodes from your search on each iteration.
• Lookup is an O(log(n)) operation in a binary search tree.
• Lookup is only O(log(n)) if you can guarantee that the number of nodes remaining to be searched will be halved or nearly halved on each iteration.

So, while it admits in that last quote that a BST may not be balanced, the O(log N) property is only for those variants that are.

For non-balanced trees, the complexity (worst case) would be O(n) as you could end up with degenerate trees like:

S             D
 \           /
  x         x
   \         \
    x         x
     \         \
      x         x
       \         \
        x         x
       /           \
      D             S

Answer 2

I think, We can find the next highest node by simply finding the Inorder Successor of the node.

Steps -

• Firstly, go to the right child of the node.
• Then move as left as possible. When you reach the leaf node, print that leaf node as that node is your next highest node compared to the given node.