285. Inorder Successor in BST


Problem Description

The problem is set within the context of a binary search tree (BST), a type of binary tree where each node has the following properties:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.

Given such a tree and a particular node p in it, you need to find the "in-order successor" of that node. The in-order successor for a given node p in a BST is defined as the node with the smallest key that is greater than p.val. If such a node doesn't exist, in other words, if p is the node with the highest value in the tree, the function should return null.

The in-order traversal of a BST produces the node values in an ascending order. So the task could also be seen as finding the next node in the in-order traversal sequence.

Intuition

When trying to understand the solution, it's critical to grasp what it means by in-order traversal and how the properties of a binary search tree can streamline our search for the successor node.

The in-order traversal for a BST involves visiting the left subtree, then the node itself, and then the right subtree. When looking for the successor of node p, if p has a right subtree, then the successor would be the leftmost node in that right subtree. If p does not have a right subtree, the successor would be one of its ancestors, specifically the one for whom p is situated in the left subtree.

The proposed solution uses this understanding and traverses the tree starting from the root. At each step, it compares the current node's value to p.val to decide the direction of the search:

  • If the current node's value is greater than p.val, the current node is a potential successor, and we go left to find a smaller one that is still larger than p.val.
  • If the current node's value is less than or equal to p.val, the current node can't be the successor, and we go right to find a larger one.

The variable ans is used to keep track of the latest potential successor. This works because of the BST property: going left finds smaller keys and going right finds larger keys. When the algorithm finishes traversing the tree (root becomes None), the ans variable either contains the in-order successor node or remains None, meaning there is no successor (if p is the maximum element).

This algorithm ensures that we only travel down the tree once, providing an efficient solution with O(h) time complexity, where h is the height of the tree.

Learn more about Tree, Depth-First Search, Binary Search Tree and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Solution Approach

The implementation of the solution follows a straightforward approach utilizing the binary search tree properties to efficiently find the in-order successor.

Firstly, let's outline the core components of the algorithm:

  • While Loop: The algorithm uses a loop to iterate through the nodes of the tree, starting at the root. The loop continues until root becomes None, which means we have reached the end of our search path in the BST.
  • Conditional Checking: Inside the loop, a conditional check compares the current node's value (root.val) with the value of the node p (p.val). This comparison dictates the traversal direction because of the binary search tree arrangement.
  • Potential Successor Update (ans): If the current node's value is greater than p.val, it means this node could potentially be the successor. We store this node to ans and continue searching to the left for a smaller value that would still be larger than p.val.
  • Traversal Direction:
    • If root.val > p.val, we move left (root = root.left) in search of a smaller yet greater value than p.val.
    • If root.val <= p.val, we move right (root = root.right) since we know that all values in the left subtree are smaller and cannot be the successor.

The algorithm makes use of the BST property that left descendants are smaller and right descendants are larger than the node itself. Hence, we can discard half of the tree in each step of the while loop, similar to a binary search.

There is no need to keep track of already visited nodes because the potential successor (ans) is updated only when moving left, ensuring that we always have the closest higher value to p.val.

Additionally, no extra data structures are required, and the solution makes in-place updates without modifying the tree, hence the space complexity is O(1).

The algorithm terminates when we can no longer traverse the tree (when root is None), which means we can return the ans value as the in-order successor. If no such successor exists (i.e., p is the maximum value in the BST), the ans remains None, which the function returns as specified.

Here's a closer look at the code snippet which encapsulates the algorithm:

1class Solution:
2    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
3        ans = None
4        while root:
5            if root.val > p.val:
6                ans = root
7                root = root.left
8            else:
9                root = root.right
10        return ans

The single pass through the tree and constant time operations on each node's value guarantee the solution is time-efficient, running in O(h) time where h is the height of the tree. This effectively means that in the worst case scenario (a skewed tree), where the tree shape resembles a linked list, the algorithm could take O(n) time where n is the number of nodes, since the tree's height would be equivalent to the number of nodes.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Example Walkthrough

Let's illustrate the solution approach using a simple binary search tree and following the steps to find the in-order successor of a given node p. Consider the following BST:

1      4
2     / \
3    2   6
4   / \ / \
5  1  3 5  7

Let's find the in-order successor of the node p with a value of 3.

  1. We start at the root of the tree, which is the node with the value 4.
  2. We compare p.val (which is 3) with root.val (which is 4).
    • Since 4 is greater than 3, the node with 4 could be the in-order successor. We save this node and move to the left to look for an even closer value greater than 3.
  3. Now, root is at the node with the value 2.
  4. We compare p.val with the new root.val (2).
    • Since 2 is less than 3, we discard the left subtree including the current node and move right to find a larger value.
  5. However, the right child of 2 is the node p itself. So, we move to the right subtree of p.
  6. Because p doesn't have a right subtree, our loop terminates, and we return the stored ans, which is 4.

In this example, the in-order successor of node p with value 3 is the node with value 4.

Here's a breakdown of how the code snippet implements this logic:

1class Solution:
2    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
3        ans = None
4        while root:
5            if root.val > p.val:
6                ans = root  # Potentially a successor, so we update `ans`.
7                root = root.left  # Search for an even closer value on the left.
8            else:
9                root = root.right  # Current or left values are not greater, we go right.
10        return ans

This walk-through demonstrates the algorithm's ability to leverage the BST properties to efficiently find the in-order successor with minimal time complexity.

Not Sure What to Study? Take the 2-min Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Python Solution

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, value):
4        self.val = value
5        self.left = None
6        self.right = None
7
8
9class Solution:
10    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
11        # Initialize variable to store the inorder successor
12        successor = None
13      
14        # Traverse the tree starting with the root
15        while root:
16            # If current node's value is greater than 'p's value,
17            # tentative successor is found (potentially there could be a closer one).
18            if root.val > p.val:
19                successor = root
20                # Move to the left subtree to find the closest ancestor
21                root = root.left
22            else:
23                # If current node's value is less than or equal to 'p's value,
24                # the successor must be in the right subtree.
25                root = root.right
26      
27        # Return the successor node
28        return successor
29

Java Solution

1// Definition for a binary tree node.
2class TreeNode {
3    int val;
4    TreeNode left;
5    TreeNode right;
6
7    TreeNode(int x) {
8        val = x;
9    }
10}
11
12class Solution {
13  
14    /**
15     * Finds the inorder successor of a given node in a BST.
16     * The inorder successor of a node is the node with the smallest key greater than the current node's key.
17     * 
18     * @param root the root of the BST
19     * @param p the target node for which we need to find the inorder successor
20     * @return the inorder successor node if exists, otherwise null
21     */
22    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
23        TreeNode successor = null; // This will hold the successor as we traverse the tree
24
25        while (root != null) {
26            if (root.val > p.val) {
27                // If current node's value is greater than p's value,
28                // go left to find a smaller value, but closer to p's value than the current value.
29                successor = root; // The potential successor is updated
30                root = root.left;
31            } else {
32                // If current node's value is less than or equal to p's value,
33                // successor must be in the right subtree.
34                root = root.right;
35            }
36        }
37
38        return successor; // Return the successor found during traversal
39    }
40}
41

C++ Solution

1/**
2 * The function `inorderSuccessor` finds the in-order successor of a given node `p`
3 * in a binary search tree. The in-order successor of a node is defined as the 
4 * node with the smallest key greater than `p->val`. The BST property is utilized here,
5 * which implies that the in-order successor of `p` is either in `p`'s right subtree
6 * (if it exists, the leftmost node there), or it's the nearest ancestor whose left child
7 * is also an ancestor of `p`.
8 *
9 * @param root: A pointer to the root node of the binary search tree.
10 * @param p: A pointer to the node in the binary search tree whose successor is to be found.
11 * @return A pointer to the in-order successor node of `p` if it exists, or `nullptr` if `p` has no in-order successor in the tree.
12 */
13class Solution {
14public:
15    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
16        TreeNode* successor = nullptr;
17      
18        while (root != nullptr) {
19            // If the current node's value is greater than that of p, then the successor must be in the left subtree
20            // (or the current node itself could be a potential successor).
21            if (root->val > p->val) {
22                successor = root; // Update potential successor
23                root = root->left; // Move left to find smaller value
24            } else {
25                // If the current node's value is not greater than that of p, move to the right subtree to find a greater value.
26                // Note: This means 'root' cannot be the successor, as its value is not greater than the 'p' value
27                root = root->right;
28            }
29        }
30        // Return the last recorded potential successor which is the actual in-order successor if it exists.
31        return successor;
32    }
33};
34

Typescript Solution

1/**
2 * Finds the in-order successor of a given node in a binary search tree (BST).
3 * In a BST, the in-order successor of a node is the node with the smallest key greater than the input node's key.
4 *
5 * @param {TreeNode | null} root - The root node of the BST.
6 * @param {TreeNode | null} targetNode - The node whose in-order successor is to be found.
7 * @return {TreeNode | null} The in-order successor node if it exists, otherwise null.
8 */
9function inorderSuccessor(root: TreeNode | null, targetNode: TreeNode | null): TreeNode | null {
10    // Variable to hold the in-order successor as we traverse the tree.
11    let successor: TreeNode | null = null;
12
13    // Loop through the tree starting from the root.
14    while (root !== null) {
15        // If the current node's value is greater than the targetNode's value,
16        // then this node could be the successor. We also move to the left child,
17        // because if there is a smaller value than the current node's value that
18        // is still larger than the targetNode's value, it would be in the left subtree.
19        if (root.val > targetNode.val) {
20            successor = root;
21            root = root.left;
22        } else {
23            // If current node's value is less than or equal to the targetNode's value,
24            // we move to the right child to look for a larger value.
25            root = root.right;
26        }
27    }
28
29    // Return the found successor, which might be null if there's no successor in the tree.
30    return successor;
31}
32
Fast Track Your Learning with Our Quick Skills Quiz:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Time and Space Complexity

The time complexity of the given code is O(h) where h is the height of the binary search tree. This is because in the worst case, the while loop will traverse from root to the leaf, following one branch and visiting each level of the tree once.

The space complexity of the given code is O(1) because it does not use any additional space that is dependent on the size of the input tree. It only uses a fixed number of pointers regardless of the number of nodes in the tree.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫