• 0

Find next higher key in Binary Search Tree with parent pointer given
  • node
  • binarysearchtree
  • binarytree
  • key
  •   
    subscribe
  • Posted: 7 years ago
  • Updated: 6 years ago
  • Edit
  • answers (1)
  • views (11623)

You are given a binary search tree. Design an algorithm to find the next higher key of a given node. Assume that the parent pointer is given.


Posted Answers

  • Posted: 7 years ago
  • 0 0
  • Edit

Let us assume that every node in the tree has parent pointer along with left child pointer, right child pointer and
its data. The algorithm works as :


  • If the given node has no right child :

      Go to the root of the given node until it is the left child of any node. That node will be the next higher node in the tree.

  • If the given node has right child :

    • If the right child of the given node has no left child

        The right child will be the next higher node.

    • If the right child of the given node has left child

        The leftmost leaf node will be the next higher node.



Example -

If the given node is \( 3 \) : Since node \( 3 \) has right child node \( 6 \) and node \( 6 \) has left child node \( 4 \), the leftmost leaf node of node \( 6 \) will be the next higher key node \( 4 \) .
If the given node is \( 8 \) : Since node \( 8 \) has right child node \( 10 \) and node \( 10 \) has no left child, node \( 10 \) will be the next higher key.
If the given node is \( 2 \) : Since node \( 2 \) has no has right child, its parent node \( 3 \) will be the next higher key because node \( 3 \) is the left child of node \( 8 \).

Time complexity = \( O(height) \).

public static TreeNode findNextHigherNodeInBST(TreeNode node){

     /* Empty Tree */
     if (node == null)
        return null;

     /* If the given node has right child  */
     if (node.right() != null)
        return findLeftMostNode(node.right());

     /* When the given node has no right child  */
     /* Go up till node is the first left child - return node's parent */
     TreeNode parent = node.parent();
     while (parent != null  & &  node == parent.right()){
        node = parent;
        parent = parent.parent();
     }
        // Intuition: as we traverse left up the tree we traverse smaller values
        // The first node on the right is the next larger number
     return parent;
 }

 public static Node findLeftMostNode(Node node){

      if(node == null)
           return null;

      /* Go to the leftmost leaf node */
      while(node.left != null)
           node = node.left;

      /* Return the leftmost node */
      return node;
 }
You need to Sign In to post your solution.