Find next higher key in Binary Search Tree when the parent pointer is not given
  • node
  • binarysearchtree
  • binarytree
  • key
  •   
  • Posted: 4 years ago
  • Updated: 3 years ago
  • Edit
  • answers (1)
  • views (2749)

Modify your algorithm in Find next higher key in Binary Search Tree with parent pointer given when the parent pointer is not given.


Posted Answers

If the parent pointer of the node is not available, we can find the next higher key by the following algorithm :


  • If the given node has right child :

      The leftmost leaf node of the right child will be the next higher node.

  • If the given node has no right child :

    • Start from the root and move towards the leaf nodes.
    • If the value at the root is less than the value at the node - Go right.
    • Otherwise, go left.


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

public static TreeNode findNextHigherNodeInBST(TreeNode node, TreeNode root){

/* 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 */
TreeNode nextHigherKey = null;

while (root != null){
if (node.data < root.data){
nextHigherKey = root;
root = root.left;
}
else if (node.data > root.data)
root = root.right;
else
break;
}

return nextHigherKey;
}

You need to Sign In to post your solution.