Problem Description

We are given a binary search tree and a node (let's call it p) in it. The task is to find the in-order successor of p in the binary search tree. The in-order successor of a node p is the node with the smallest key greater than p.val.

If the given node p does not have an in-order successor in the tree, we should return null or None.

Let's go through an example:

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

In this case, the binary search tree is like this:

1
2
3  2
4 / \
51   3

The in-order traversal of the tree gives us a sorted list of nodes: [1, 2, 3]. For p which equals to 1, the in-order successor is 2. Therefore, the output is 2.

Solution Approach

To solve this problem, we can use a recursive approach with binary search property in mind.

Here is the core idea:

• If root equals null, then return null. Because there is no node in the tree.
• If root's value (root.val) is less than or equal to p.val, the in-order successor can only be in the right subtree. So we should check the right subtree.
• Otherwise, there could be two situations:
  • There is an in-order successor in the left subtree.
  • There is no in-order successor in the left subtree, so the root node itself is the in-order successor.

With this approach, we need to traverse at most h nodes (with h being the height of the tree), so the time complexity is O(h). And the space complexity is O(h) due to the function call stack (in case of a skewed binary tree).

Python Solution

1
2python
3class TreeNode:
4    def __init__(self, x):
5        self.val = x
6        self.left = None
7        self.right = None
8
9class Solution:
10    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
11        if root is None:
12            return None
13        if root.val <= p.val:
14            return self.inorderSuccessor(root.right, p)
15        
16        left = self.inorderSuccessor(root.left, p)
17        return left if left is not None else root

Java Solution

1
2java
3public class TreeNode {
4    int val;
5    TreeNode left;
6    TreeNode right;
7    TreeNode(int x) { val = x; }
8}
9
10public class Solution {
11    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
12        if (root == null)
13            return null;
14        if (root.val <= p.val)
15            return inorderSuccessor(root.right, p);
16        
17        TreeNode left = inorderSuccessor(root.left, p);
18        return left != null ? left : root;
19    }
20}

JavaScript Solution

1
2javascript
3function TreeNode(val, left, right) {
4    this.val = (val===undefined ? 0 : val)
5    this.left = (left===undefined ? null : left)
6    this.right = (right===undefined ? null : right)
7}
8
9var inorderSuccessor = function(root, p) {
10    if (root === null)
11        return null;
12    if (root.val <= p.val)
13        return inorderSuccessor(root.right, p);
14    
15    const left = inorderSuccessor(root.left, p);
16    return left !== null ? left : root;
17};

C++ Solution

1
2cpp
3struct TreeNode {
4    int val;
5    TreeNode *left;
6    TreeNode *right;
7    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8};
9
10class Solution {
11public:
12    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
13        if (root == nullptr)
14            return nullptr;
15        if (root->val <= p->val)
16            return inorderSuccessor(root->right, p);
17        
18        TreeNode* left = inorderSuccessor(root->left, p);
19        return left != nullptr ? left : root;
20    }
21};

C# Solution

1
2csharp
3public class TreeNode {
4    public int val;
5    public TreeNode left;
6    public TreeNode right;
7    public TreeNode(int x) { val = x; }
8}
9
10public class Solution {
11    public TreeNode InorderSuccessor(TreeNode root, TreeNode p) {
12        if (root == null)
13            return null;
14        if (root.val <= p.val)
15            return InorderSuccessor(root.right, p);
16        
17        TreeNode left = InorderSuccessor(root.left, p);
18        return left != null ? left : root;
19    }
20}

Swift Solution

1
2swift
3public class TreeNode {
4    public var val: Int
5    public var left: TreeNode?
6    public var right: TreeNode?
7    public init(_ val: Int) {
8        self.val = val
9        self.left = nil
10        self.right = nil
11    }
12}
13
14class Solution {
15    func inorderSuccessor(_ root: TreeNode?, _ p: TreeNode) -> TreeNode? {
16        if root == nil {
17            return nil
18        }
19        if root!.val <= p.val {
20            return inorderSuccessor(root!.right, p)
21        }
22
23        let left = inorderSuccessor(root!.left, p)
24        return left != nil ? left : root
25    }
26}

In the Swift solution, we define a TreeNode class with three properties: val, left, and right. The inorderSuccessor function uses the same logic described previously. We first check if the root is equal to nil. If it is, we return nil. If the root's val is less than or equal to p.val, we recursively call the function on the right node. Otherwise, we recursively call the function on the left node. If the call to the left node returns nil (which means the left subtree does not have an in-order successor), we return the root.

That wraps up our discussion on finding the In-Order Successor in a Binary Search Tree. We have covered the problem, the approach to solve it and we have shown solutions in Python, JavaScript, Java, C++, C#, and Swift. We hope this article has been helpful and has given you a firm understanding of this common interview problem.