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.
Let us assume that every node in the tree has parent pointer along with left child pointer, right child pointer and
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){ |