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 II

Number: 509

Difficulty: Medium

Paid? Yes

Companies: Meta, Arista Networks, Microsoft

Problem Description

Given a node in a binary search tree where each node has a pointer to its parent, find the in-order successor of that node. The in-order successor is the node with the smallest key greater than the current node's value. If no such node exists, return null.

Key Insights

  • If the given node has a right child, the successor is the leftmost node in the right subtree.
  • If the node does not have a right child, move up the tree using the parent pointer until you find a node that is a left child of its parent. That parent node is the successor.
  • If no suitable parent is found, the given node is the largest element and its successor is null.

Space and Time Complexity

Time Complexity: O(h), where h is the height of the tree. Space Complexity: O(1) using a constant amount of extra space.

Solution

We leverage the properties of a BST along with parent pointers. The algorithm first checks if the node has a right subtree. If yes, it finds the leftmost node in that subtree which is the in-order successor. If there is no right subtree, we traverse up using parent pointers until we find a node that is the left child of its parent, which indicates that the parent's value is the next greater element in the in-order traversal.

Code Solutions

# Python solution with line-by-line comments

class Node:
    def __init__(self, val):
        self.val = val          # Node value
        self.left = None        # Left child node
        self.right = None       # Right child node
        self.parent = None      # Parent node

def inorderSuccessor(node):
    # If there is a right subtree, find its leftmost node.
    if node.right:
        successor = node.right
        # Loop to find the leftmost child
        while successor.left:
            successor = successor.left
        return successor
    # If no right subtree, traverse up using parent pointers.
    parent = node.parent
    while parent and node == parent.right:
        node = parent
        parent = parent.parent
    return parent  # This will be the in-order successor or None if not found
← Back to All Questions