LeetCode 510: Inorder Successor in BST II

Problem Restatement

We are given a node in a binary search tree.

Each node contains:

We need to return the inorder successor of the given node.

The inorder successor of a node is the next node visited during inorder traversal:

left -> root -> right

If no successor exists, return None.

The official problem provides parent pointers and asks for the next node in inorder traversal order. (leetcode.com)

Input and Output

Function shape:

class Solution:
    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':
        ...

Examples

Example 1:

      5
     / \
    3   6
   / \
  2   4
 /
1

Suppose the input node is:

3

The inorder traversal is:

1, 2, 3, 4, 5, 6

The next node after 3 is:

4

So the answer is node 4.

Example 2:

      2
     / \
    1   3

If the input node is:

3

then 3 is the final node in inorder traversal.

So the answer is:

None

First Thought: Build the Entire Inorder Traversal

One possible solution is:

1. Find the tree root.
2. Perform full inorder traversal.
3. Store nodes in an array.
4. Locate the target node.
5. Return the next array element.

This works, but it uses unnecessary extra memory.

The parent pointer gives us enough information to move upward directly.

Key Insight

There are only two cases.

Case 1: The node has a right subtree

If the node has a right child, then the successor is:

the leftmost node in the right subtree

Example:

    5
     \
      8
     /
    6

The successor of 5 is 6.

We move right once, then go left as far as possible.

Case 2: The node has no right subtree

Then we move upward using parent pointers.

We continue climbing while the current node is the right child of its parent.

The first parent where we arrive from the left side is the successor.

Example:

      5
     /
    3
     \
      4

The successor of 4 is 5.

We move upward from 4.

4 is a right child of 3, so continue upward.

3 is a left child of 5, so 5 is the successor.

Algorithm

If the node has a right child:

1. Move to node.right
2. Continue moving left until no left child exists
3. Return that node

Otherwise:

1. While:
   • node.parent exists
   • and node is the right child of its parent
2. Move upward
3. Return node.parent

If we reach the top without finding such a parent, return None.

Correctness

Inorder traversal visits nodes in this order:

left subtree -> node -> right subtree

If a node has a right subtree, the next visited node must be the leftmost node inside that right subtree. No smaller node there can appear after the current node.

If a node does not have a right subtree, then its successor must lie among its ancestors.

Moving upward from a right child means the ancestor and its left subtree have already been fully visited, so traversal continues upward.

The first ancestor reached from the left side is the first node whose inorder visit occurs after the current node.

If no such ancestor exists, then the current node is the rightmost node in the BST and has no inorder successor.

Therefore the algorithm always returns the correct inorder successor or None.

Complexity

Here:

h = tree height

Implementation

# Definition for a Node.
# class Node:
#     def __init__(self, val):
#         self.val = val
#         self.left = None
#         self.right = None
#         self.parent = None

class Solution:
    def inorderSuccessor(self, node: 'Node') -> 'Node':
        # Case 1:
        # Right subtree exists
        if node.right:
            current = node.right

            while current.left:
                current = current.left

            return current

        # Case 2:
        # Move upward
        while node.parent and node == node.parent.right:
            node = node.parent

        return node.parent

Code Explanation

First check whether the node has a right subtree:

if node.right:

If it does, move right once:

current = node.right

Then move left as far as possible:

while current.left:
    current = current.left

The leftmost node is the inorder successor.

If no right subtree exists, move upward:

while node.parent and node == node.parent.right:

As long as the current node is a right child, its parent has already been visited during inorder traversal.

So continue climbing upward:

node = node.parent

When the loop stops:

return node.parent

returns the first ancestor reached from the left side.

If no such ancestor exists, node.parent is None.

Testing

def connect(parent, left=None, right=None):
    parent.left = left
    parent.right = right

    if left:
        left.parent = parent

    if right:
        right.parent = parent

def test_inorder_successor():
    s = Solution()

    # Tree:
    #       5
    #      / \
    #     3   6
    #    / \
    #   2   4
    #  /
    # 1

    n1 = Node(1)
    n2 = Node(2)
    n3 = Node(3)
    n4 = Node(4)
    n5 = Node(5)
    n6 = Node(6)

    connect(n5, n3, n6)
    connect(n3, n2, n4)
    connect(n2, n1)

    assert s.inorderSuccessor(n3).val == 4
    assert s.inorderSuccessor(n4).val == 5
    assert s.inorderSuccessor(n1).val == 2
    assert s.inorderSuccessor(n6) is None

    print("all tests passed")

Test meaning: