Challenge 🤔

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

The successor of a node p is the node with the smallest key greater than p.val. In other words: A successor is the node that would appear right after our target node in an inorder traversal.

Example 1

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

Output: 2

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 = [5,3,6,2,4,null,null,1], p = 6

Output: null

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 successor in the tree, return null.
• It’s guaranteed that the values of the tree are unique.

Real World Applications 🌎

In order successor 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 successor. 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 successor is the first node after our target node when traversing our tree in an ascending manner. Because the successor is larger than our target it will never be in the left sub tree, so let’s ignore that. There are two distinct cases we need to account for:

1) Target Node has right child

Binary search trees are sorted by defintion, such that the right child is always larger than the parent node. So this is the simple case! If our target node has a right subtree we can return smallest node in the right subtree!

2) Target Node has no right 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! 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.

However, this is suboptimal in terms of space complexity as we are required to allocate O(n) extra space.

Naive Solution 💡

Complexity Analysis 🧮

Time complexity

O(n)

One set of constant operations for every node. At worst we traverse the whole tree once.

Space complexity

O(n)

Optimal Solution 💡

Let’s try a different approach. We can traverse our sorted tree. As soon as we hit the first node that has a larger value than target let’s save it. At this point, we can try and traverse the left subtree (if it exists!) to find the smallest node that is still larger than target. This is a better approach because we don’t need to allocate any extra space!

Complexity Analysis 🧮

Time complexity

O(n)

One set of constant operations for every node. At worst we traverse the whole tree once.

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.

Resources 📚 💻

• Leetcode- Inorder Successor in BST