Prerequisites :- Binary Search Trees, BT traversals.
Problem :- Find the inorder predecessor of a given node X in a binary search tree. The inorder predecessor, denoted as node Y, is the node that immediately precedes X in the inorder traversal of the binary tree. If no such predecessor exists, return -1.
Solution Approach :-
The solution uses an iterative approach to find the inorder predecessor of a given node in a Binary Search Tree (BST). The key observation is that the inorder predecessor is the largest node in the left subtree of the given node (if it has a left subtree). If the given node doesn’t have a left subtree, we need to traverse up the tree until we find a node whose right child is an ancestor of the given node.
Algorithm:
-
- Initialize a pointer predecessor to NULL.
-
- Iterate through the tree:
- If the current node’s value is less than the target value x, update the predecessor and move to the right subtree.
- If the current node’s value is greater than or equal to x, move to the left subtree.
-
- After the iteration, if the predecessor is still NULL, return -1 as no predecessor exists. 4. Otherwise, return the value of the predecessor.
Time complexity: O(N), because in the worst case, the algorithm visits all the nodes in the given BST.
Space complexity: O(1), as no extra space is needed.