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

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

 Posted: 4 years ago Updated: 4 years ago 0 0 Edit 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; }