Challenge 🤔

Given a binary search tree and a node in it, find the in-order predecessor of that node in the BST.

The predecessor of a node p is the node with the largest key smaller than p.val. In other words: A predecessor is the node that would appear right before our target node in an inorder traversal.

Let’s even make an analogy for this (aka poor excuse to use a gif)

predecessor -> current node

yesterday -> today

Example 1

Input: root = [2,1,3], p = 2

Output: 1

Explanation

1’s in-order successor node is 2. Note that both p and the return value is of TreeNode type.

Example 2

Input: root = [3,2,4,1,null,null, ], p = 3

Output: 2

Explanation

There is no in-order successor of the current node, so the answer is null.

Note

• If the given node has no in-order predecessor in the tree, return null.
• It’s guaranteed that the values of the tree are unique.
• This is the inverse of the Find Successor in BST exercise!

Real World Applications 🌎

In order predecessor is an important concept to understand because it is needed in when we want to implement basic tree functionalities such as deleting a node from a BST. Additionally, when discussing a sorted data structure, there are many use cases for knowing which node is the predecessor. I’ll let you be creative with this one ;)

The Finer Details 🔎

Inorder traversal gives us all the nodes in the tree in ascending order. Inorder predecessor is the last node before our target node when traversing our tree in an ascending manner. Because the predecessor is smaller than our target it will never be in the right sub tree, so let’s ignore that. There are two distinct cases we need to account for:

1) Target Node has left child

Binary search trees are sorted by defintion, such that the left subtree holds nodes smaller than the parent node. So this is the simple case! If our target node has a left subtree we can return largest node in the left subtree!

2) Target Node has no left child

In this case, we’re looking for the first ancestor which is a left parent of our current node. In other words, the first node that is larger than target.

There are a few ways we can do this!

Naive Solution 💡 - Inorder Traversal With Stack

The easiest to conceptualize is keeping a stack of all visited nodes. When we reach our target node, we can keep popping off nodes from the stack until we find the first “left parent”. Let’s see this.

Solution 💡 - Search in BST

The easiest way to understand the iterative version of this is to think about binary search. We’ll start searching through the tree and always rememember the last node we’ve seen that is still smaller than our target. It only makes sense that we should use binary search on a binary search tree right?

Complexity Analysis 🧮

Time complexity O(n), One set of constant operations for every node.

Space complexity O(1) -> No extra space allocated!

Takeaways 🎉🥳

The main takeaways here are finding the next node in a binary search tree. Remember, next must always be larger, so it will never be in the left sub tree! Next is either:

1. The smallest largest node is the leftest node in the right subtree
2. The first parent that has target as a left child.