Vultr DocsLatest Content

Inorder Successor in BST

Updated on 06 June, 2025
Inorder Successor in BST header image

Problem Statement

In the given problem, we need to find the in-order successor of a specified node p in a binary search tree (BST). The in-order successor of a node p is defined as the node with the smallest key that is greater than p.val. If node p does not have a successor, the function should return null. The input to the function includes the root of the binary search tree and the target node p. Understanding the successor in a BST context is essential because it defines an inherent order among the nodes, where each node's successor is the next node in the arithmetic ordering of the keys.

Examples

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`.

Constraints

  • The number of nodes in the tree is in the range [1, 104].
  • -105 <= Node.val <= 105
  • All Nodes will have unique values.

Approach and Intuition

The approach to find the in-order successor of a node in a binary search tree combines knowledge of tree traversal and BST properties. The in-order traversal of a BST yields the nodes in ascending order, which directly helps in understanding and identifying the successor.

  1. Node with a Right Child:
    If the node p has a right child, the in-order successor is the left-most node of the right subtree of p. This is because, in in-order traversal, we visit the left child, the node itself, and then the right child. Therefore, the smallest node greater than p must be the left-most node of its right subtree.

  2. Node without a Right Child:
    If the node p has no right child, the successor is up the tree. We start from the root and move down. We maintain a variable (say successor). If the current node in our traversal is greater than p, we update successor to this node and move to the left child. If it’s smaller, we move to the right child. This is repeated until all possibilities are exhausted.

Examples Explained

  • Example 1 - Input: root = [2,1,3], p = 1:

    • Node 1 has no right child. Starting from the root, which is 2 (greater than 1), we move to the left child 1. Since 1 is the target itself and it has no right child, its successor, recorded during the traversal (2), is the answer.

  • Example 2 - Input: root = [5,3,6,2,4,null,null,1], p = 6:

    • Node 6 has no right child and there’s no greater node while tracing back to the root. Each ancestor of 6 is either smaller or is 6 itself. Thereby, 6 has no in-order successor in this arrangement, resulting in null.

This approach uses the inherent structure of BST for efficient resolution of the successor, leveraging in-order traversal principles and properties of BST.

Solutions

  • Java
  • Python
java 
class Solution {

    public TreeNode findInorderSuccessor(TreeNode root, TreeNode p) {

        TreeNode next = null;

        while (root != null) {

            if (p.val >= root.val) {
                root = root.right;
            } else {
                next = root;
                root = root.left;
            }
        }

        return next;
    }
}

This Java solution involves finding the inorder successor of a given node p in a binary search tree (BST). The approach uses a while loop to traverse the BST starting from the root. It explicitly checks the value of node p against the current node value (root.val). If the value of p is greater than or equal to the current node’s value, the search moves to the right subtree, since the inorder successor must be a higher value. If the value of p is less than the current node’s value, the current node might potentially be the inorder successor, so it is temporarily stored in next, and the search continues in the left subtree to find a closer successor, if any. The search stops when root becomes null, and the next node, which holds the potential successor, is returned.

Key takeaways:

  • Navigate the right subtree when the target node’s value is greater than the current node.
  • Save and update the potential successor (next) as you navigate to the left subtree looking for a lower possible successor node.
  • Return the node stored in next as the inorder successor of node p.

This algorithm efficiently searches for the inorder successor in O(h) time complexity, where h is the height of the tree, by leveraging the properties of BSTs.

python 
class Solution:
    
    def findSuccessor(self, node: 'TreeNode', target: 'TreeNode') -> 'TreeNode':
        
        next_node = None
        
        while node:
            
            if target.val >= node.val:
                node = node.right
            else:
                next_node = node
                node = node.left
                
        return next_node

In Python3, the given code defines a method to find the inorder successor of a target node in a Binary Search Tree (BST). The function findSuccessor takes two parameters: the root of the tree (node) and the node for which the successor needs to be found (target). The method utilizes the properties of the BST to efficiently determine the inorder successor.

Here's a breakdown of how the code works:

  • Initialize next_node as None to store the reference of the successor as it's found.

  • The function uses a while loop to traverse the tree starting from the root node. The traversal continues until the current node becomes None, indicating you've reached beyond the leaf nodes where the successor might have been found.

  • Within the loop:

    • If the value of the target node is greater than or equal to the current node's value, the code moves to the right subtree (node = node.right) because the inorder successor will be in the right subtree or beyond.
    • If the target node's value is less, the current node is a potential successor. The next_node variable is updated to the current node before moving to the left subtree (node = node.left) to further search for a closer successor if it exists.

  • The loop exits when there is no more tree to traverse (node becomes None), and at this point, next_node will contain the inorder successor if one exists, or remain None if no successor exists.

  • Finally, next_node is returned.

This approach ensures that each movement in the tree narrows down the potential candidates for being the successor by utilizing the properties of the BST, resulting in an efficient O(h) time complexity solution, where h is the height of the tree.

Comments

No comments yet.