We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Inorder Successor in BST

Number: 285

Difficulty: Medium

Paid? Yes

Companies: Microsoft, Meta, Pocket Gems

Problem Description

Given the root of a Binary Search Tree (BST) and a node p in it, find the in-order successor of node p – that is, the node with the smallest value greater than p.val. If no such node exists, return null.

Key Insights

  • In a BST, an in-order traversal yields nodes in ascending order.
  • If the node p has a right subtree, the in-order successor is the left-most node in that right subtree.
  • If p has no right subtree, the successor is one of its ancestors; traverse from the root towards p while keeping track of the last node that is greater than p.
  • An iterative approach is efficient and avoids recursion stack overhead.

Space and Time Complexity

Time Complexity: O(h), where h is the height of the tree. In the worst-case (skewed tree), it can be O(n). Space Complexity: O(1) as only a constant amount of extra space is used.

Solution

We solve the problem using two cases:

  1. If node p has a right subtree, we simply find the left-most node in that right subtree.
  2. If node p does not have a right subtree, initiate a search from the BST root. As we traverse:
    • If the current node's value is greater than p.val, the current node is a candidate for the successor; move to the left subtree to look for a smaller candidate.
    • Otherwise, move to the right subtree. By the end of the traversal, the candidate (if exists) is the in-order successor. This approach benefits from the BST property, limiting traversal to O(h) time.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        # If p has a right subtree, the successor is the left-most node in that subtree.
        if p.right:
            successor = p.right
            while successor.left:
                successor = successor.left
            return successor
        
        # Otherwise, start from the root and keep track of a potential successor.
        successor = None
        current = root
        while current:
            if p.val < current.val:
                # current is a candidate, so record it and move left to find a smaller candidate
                successor = current
                current = current.left
            else:
                # If p.val is greater or equal, go right.
                current = current.right
        return successor
← Back to All Questions