**Difficulty:** Easy, **Asked-in:** Amazon, Microsoft, Ola.

**Key takeaway:** An excellent problem to learn problem-solving using both iterative and recursive approaches in the binary search tree.

Write a program to find the in-order predecessor of a given node x in a binary search tree (BST). An in-order predecessor of node x is the node that will be visited just before node x in the in-order traversal.

**Problem note:** If node x is visited first (leftmost node in BST), then the predecessor of node x is NULL. In other words, the in-order predecessor of the node with the minimum value does not exist in the BST.

If the left subtree of node x is present, the in-order predecessor of node x is a node with the maximum value in its left subtree. If the left subtree of node x doesn't exist, then there are two cases:

- If node x is the right child of its parent, then the in-order predecessor will be its parent node.
- If node x is the left child of its parent, the in-order predecessor will be one of the ancestors. To find such an ancestor, we traverse up the tree towards the root until we encounter a node y that is the right child of its parent. If such a node y is present, then the in-order predecessor of x is the parent of node y.

The critical question is: How can we move up in the BST? To implement this, we include a parent pointer in the BST node structure, which points to the parent of the given node.

**If (x->left != NULL)**, we find the maximum node in the left subtree and return it as the predecessor, i.e.,**return bstMaximum(x->left**).- Otherwise,
**if(x->parent != NULL && x->parent->right == x)**, we return x->parent as the predecessor. - Otherwise, we need to find the first ancestor of node x which is the right child of its parent. If such a node is present, then the in-order predecessor is its parent. To find this:
- We start by initializing a pointer
**curr**with node x and a pointer**p**to the parent of node x. - We now run a loop as long as
**p**is not NULL and**curr**is the left child of its parent (**p->left == curr**). - Within the loop, we continue moving up by updating curr to p and p to its parent (
**p = p->parent**). - At the end of the loop,
**curr**will be the first ancestor of node x which is the right child of its parent, and**p**will be its parent. So, we return pointer**p**as the predecessor.

```
BSTNode* bstMaximum(BSTNode* root)
{
while (root->right != NULL)
root = root->right;
return root;
}
BSTNode* inorderPredecessor(BSTNode* x)
{
if (x == NULL)
return NULL;
if (x->left != NULL)
return bstMaximum(x->left);
else if(x->parent != NULL && x->parent->right == x)
return x->parent;
else
{
BSTNode* p = x->parent;
BSTNode* curr = x;
while (p != NULL && p->left == curr)
{
curr = p;
p = p->parent;
}
return p;
}
}
```

```
def bstMaximum(root):
while root.right is not None:
root = root.right
return root
def inorderPredecessor(x):
if x is None:
return None
if x.left is not None:
return bstMaximum(x.left)
elif x.parent is not None and x.parent.right == x:
return x.parent
else:
p = x.parent
curr = x
while p is not None and p.left == curr:
curr = p
p = p.parent
return p
```

If the left child of node x is present, then the maximum value in the left subtree will be the predecessor. In the worst case, node x will be the root node and the node with minimum value in the left subtree is the deepest leaf node. Here we need to traverse the complete height of the tree. So the time complexity in the worst case = O(h).

If the left child of x is not present, then we traverse up to find the predecessor. In the worst case, x will be one of the deepest leaf nodes, and the root node will be the predecessor. Here, we need to traverse the complete height of the tree. So the time complexity in the worst case = O(h).

Overall, the time complexity will be O(h), which depends on the height of the tree. Since we are storing an extra parent pointer inside each node, the space complexity = O(n).

Storing a parent pointer inside the BST node helps us easily traverse up the tree, but it requires O(n) extra space. Now, the critical question is: Can we solve this problem without using a parent pointer? Let’s think!

The idea is: We maintain a **pred** pointer to track the predecessor and move down from the root to node x by comparing the root->key with the x->key.

**If x->key < root->key**, we move left. There is no need to update the**pred**pointer because the current node**root**will not be the candidate for the predecessor. The idea is simple: the value of the**pred->key**will always be less than the**x->key**.**If x->key > root->key**, we update the**pred**pointer to the current node**root**and move to the right subtree (**pred = root**and**root = root->right**). We update the pred pointer because the current node root will be the candidate for the predecessor. Think!**If x->key == root->key**, we have found the node. So we check if the left subtree of node**x**exists. If it does, we update the**pred**pointer to the maximum node in the left subtree (**pred = bstMaximum(x->left)**) and break from the loop.

By the end of this loop, we return the **pred** pointer.

```
BSTNode* bstMaximum(BSTNode* root)
{
while (root->right != NULL)
root = root->right;
return root;
}
BSTNode* inorderPredecessor(BSTNode* root, BSTNode* x)
{
if (root == NULL)
return NULL;
BSTNode* pred = NULL;
while (root != NULL)
{
if (x->key < root->key)
{
root = root->left;
}
else if (x->key > root->key)
{
pred = root;
root = root->right;
}
else
{
if (root->left != NULL)
pred = bstMaximum(root->left);
break;
}
}
return pred;
}
```

```
def bstMaximum(root):
while root.right is not None:
root = root.right
return root
def inorderPredecessor(root, x):
if root is None:
return None
pred = None
while root is not None:
if x.key < root.key:
root = root.left
elif x.key > root.key:
pred = root
root = root.right
else:
if root.left is not None:
pred = bstMaximum(root.left)
break
return pred
```

During the search process, we need to traverse the entire height of the tree in the worst case. So the time complexity in the worst case = O(h). Since there is no parent pointer and we use a constant amount of extra space, the space complexity = O(1).

In the above solution, we iteratively move down the tree to search for node x and update the predecessor. The critical question is: Can we think of implementing it using recursion?

The idea is to recursively move down to search for node x in the BST and keep updating the predecessor. When we find the node x and the left subtree of node x is present, we return the node with the maximum value in the left subtree of x. If the left subtree of node x doesn't exist, then the in-order predecessor is one of its ancestors, which has already been updated while searching.

- If
**root->key == x->key**, we check if node**x**has a left subtree. If it does, we return the maximum node in the left subtree as the predecessor, i.e.,**return bstMaximum(root->left)**. - If
**root->key > x->key**, we recursively call the same function on the left subtree to continue searching for the predecessor in the left subtree, i.e.,**inorderPredecessor(root->left, pred, x)**. There is no need to update the pred pointer because pred->key will always be less than the x->key. - If
**root->key < x->key**, we update the**pred**pointer to the current node root and recursively call the same function on the right subtree, i.e.,**inorderPredecessor(root->right, pred, x)**. - Finally, we return the
**pred**pointer.

```
BSTNode* bstMaximum(BSTNode* root)
{
while (root->right != NULL)
root = root->right;
return root;
}
BSTNode* inorderPredecessor(BSTNode* root, BSTNode* pred, BSTNode* x)
{
if (root == NULL)
return NULL;
if (root->key == x->key)
{
if (x->left != NULL)
return bstMaximum(x->left);
}
else if (root->key > x->key)
return inorderPredecessor(root->left, pred, x);
else
{
pred = root;
return inorderPredecessor(root->right, pred, x);
}
return pred;
}
```

```
def bstMaximum(root):
while root.right:
root = root.right
return root
def inorderPredecessor(root, pred, x):
if root is None:
return None
if root.key == x.key:
if x.left:
return bstMaximum(x.left)
elif root.key > x.key:
return inorderPredecessor(root.left, pred, x)
else:
pred = root
return inorderPredecessor(root.right, pred, x)
return pred
```

At each step of recursion, we are going one level down. So in the worst case, we will be traversing the complete height of the tree. So time complexity = O(h).

Space complexity will depend on the size of the call stack, which will be equal to the height of the recursion tree. So space complexity = O(h).

As we know, the in-order predecessor of node x is the node that will be visited just before node x in the in-order traversal. The critical question is: Can we solve it using an in-order traversal? Here's an idea!

We traverse the BST in an in-order manner and keep track of the previous node visited. When we find the target node, the previous node represents its in-order predecessor. To ensure that the changes to the previous node are propagated correctly across the recursive calls, we use a pointer **prev** and pass it as a reference during the recursive call.

```
BSTNode* inorder(BSTNode* root, BSTNode* x, BSTNode*& prev)
{
if (root == NULL)
return NULL;
BSTNode* leftResult = inorder(root->left, x, prev);
if (leftResult != NULL)
return leftResult;
if (x->key == root->key)
return prev;
prev = root;
return inorder(root->right, x, prev);
}
BSTNode* inorderPredecessor(BSTNode* root, BSTNode* x)
{
if (root == NULL || x == NULL)
return NULL;
BSTNode* prev = NULL;
return inorder(root, x, prev);
}
```

```
def inorder(root, x, prev):
if root is None:
return None
leftResult = inorder(root.left, x, prev)
if leftResult is not None:
return leftResult
if x.key == root.key:
return prev
prev[0] = root
return inorder(root.right, x, prev)
def inorderPredecessor(root, x):
if root is None or x is None:
return None
prev = [None]
return inorder(root, x, prev)
```

In the worst case, we will traverse each node only once using an in-order traversal. So, the time complexity will be O(n) in the worst case. Inside the code, we use constant extra space, but recursion will utilize a call stack with a size equal to the height of the tree. So, the space complexity is O(h).

- How can we solve this problem using iterative in-order traversal?
- How can we modify the above code to find both the in-order successor and predecessor together?
- In the first approach using a parent pointer, is there a need to handle this condition: if (x->parent != NULL && x->parent->right == x)?
- In the second and third approaches, why do we update the pred pointer when we move to the right subtree?
- Which method is better in terms of time and space complexity?
- How can we solve this problem by storing the in-order traversal of the BST in an array?
- The time complexity of all the above approaches is O(h). What would be the worst and best-case scenarios?
- Can we consider implementing the above code in a different manner?

- Replace each node in the binary tree with the sum of its inorder predecessor and successor
- Populate Inorder predecessor for all nodes
- Find the in-order successor of a node in BST
- In-order predecessor of a node in binary tree
- The lowest common ancestor of a binary search tree
- Validate binary search tree
- The kth largest element in a BST
- Convert sorted array to binary search tree

If you have any queries or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!