Problem Description

You are given the root of a binary search tree (BST) and a specific node p within that tree. Your task is to find and return the in-order successor of node p.

The in-order successor of a node p is defined as the node that comes immediately after p when performing an in-order traversal of the BST. In simpler terms, it's the node with the smallest value that is still greater than p.val.

Key points to understand:

• In a BST, an in-order traversal visits nodes in ascending order of their values
• The successor of node p must have a value greater than p.val
• Among all nodes with values greater than p.val, the successor is the one with the minimum value
• If no such node exists (meaning p has the largest value in the tree), return null

For example, if you have a BST with values [1, 2, 3, 4, 5] and p has value 3, then the in-order successor would be the node with value 4.

The solution leverages the BST property where left children have smaller values and right children have larger values. Starting from the root, we can navigate through the tree:

• When we encounter a node with value greater than p.val, it could potentially be our answer, so we save it and explore the left subtree to find if there's a smaller valid successor
• When we encounter a node with value less than or equal to p.val, we know the successor must be in the right subtree

This approach efficiently finds the successor in O(h) time where h is the height of the tree, without needing to perform a full in-order traversal.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary search tree is a special type of graph where each node has at most two children, and nodes are connected by edges (parent-child relationships).

Is it a tree?

• Yes: The problem explicitly states we're working with a binary search tree, which is a tree data structure.

DFS

• We arrive at DFS: Since we're dealing with a tree structure, the flowchart leads us to use Depth-First Search.

Conclusion: The flowchart suggests using a DFS approach for finding the inorder successor in a BST.

The DFS pattern is indeed the correct choice here because:

1. We need to traverse the tree structure to find the successor node
2. The solution uses a modified DFS where we traverse down the tree following a specific path based on BST properties
3. At each node, we make a decision to go left or right based on comparing values, which is a depth-first exploration strategy
4. We don't need to visit all nodes - we follow a single path from root to leaf, making decisions at each level

The provided solution implements an iterative DFS that efficiently navigates through the BST by comparing the current node's value with p.val at each step, maintaining the potential successor in the ans variable as it traverses deeper into the tree.

Intuition

Let's think about what an in-order successor means in a BST. When we do an in-order traversal of a BST, we get values in ascending order. So the successor of node p is simply the next value in this sorted sequence.

But do we really need to traverse the entire tree and create a sorted list? That would be inefficient. Instead, let's leverage the BST property: for any node, all values in its left subtree are smaller, and all values in its right subtree are larger.

Starting from the root, when we encounter a node, we can ask: could this be the successor of p?

• If current.val > p.val, this node could potentially be our answer! But wait - there might be a smaller value that's still greater than p.val in the left subtree. So we save this node as a candidate and explore left.

• If current.val <= p.val, this node cannot be the successor (it's not greater than p). The successor must be somewhere in the right subtree, so we go right.

Think of it like playing a "higher or lower" game. Each time we find a value higher than p.val, we say "this could be it, but let me check if there's something smaller that still works" by going left. Each time we find a value that's not higher, we know we need to look for larger values by going right.

The beauty of this approach is that we're essentially performing a binary search on the tree. We maintain the best candidate we've seen so far (the smallest value greater than p.val), and keep refining our search until we've exhausted all possibilities. When we can't go any further (reach a null node), our saved candidate is the answer.

This way, we only visit nodes along a single path from root to leaf, giving us O(h) time complexity where h is the height of the tree, rather than O(n) if we did a full traversal.

Solution Approach

The solution implements a binary search approach on the BST to find the in-order successor efficiently.

We start with two key variables:

• ans = None: This stores our potential answer (the smallest node value greater than p.val)
• root: Our current position in the tree as we traverse

The algorithm follows a simple while loop that continues until we've exhausted all paths:

while root:
    if root.val > p.val:
        ans = root
        root = root.left
    else:
        root = root.right

Let's break down the logic:

Case 1: root.val > p.val

• The current node's value is greater than p, so it could be our successor
• We update ans = root to save this potential successor
• But there might be a smaller valid successor in the left subtree, so we move left with root = root.left
• This ensures we find the smallest value among all values greater than p.val

Case 2: root.val <= p.val

• The current node's value is not greater than p, so it cannot be the successor
• The successor must have a larger value, so we search the right subtree with root = root.right
• We don't update ans because this node doesn't satisfy our requirement

The algorithm naturally terminates when root becomes None, meaning we've reached a leaf node's child. At this point, ans contains the in-order successor if it exists, or None if no successor was found.

Why this works:

• Each time we find a node greater than p.val, we save it and try to find a smaller one by going left
• Each time we find a node not greater than p.val, we look for larger values by going right
• The last saved node in ans will be the smallest value greater than p.val, which is exactly the in-order successor

The time complexity is O(h) where h is the height of the tree, and space complexity is O(1) as we only use two variables regardless of tree size.

Example Walkthrough

Let's walk through finding the in-order successor of node p with value 6 in this BST:

        8
       / \
      3   10
     / \    \
    1   6   14
       / \
      4   7

We want to find the smallest node value greater than 6.

Initial State:

• ans = None (no candidate yet)
• root = 8 (starting at the root)
• p.val = 6

Step 1: Current node = 8

• Is 8 > 6? Yes!
• This could be our answer, so ans = 8
• But there might be a smaller valid successor in the left subtree
• Move left: root = 3

Step 2: Current node = 3

• Is 3 > 6? No
• This can't be our successor (it's smaller than 6)
• The successor must be larger, so go right
• Move right: root = 6
• Keep ans = 8 (no update)

Step 3: Current node = 6

• Is 6 > 6? No (equal values don't count)
• This can't be our successor
• Need to find something larger, so go right
• Move right: root = 7
• Keep ans = 8 (no update)

Step 4: Current node = 7

• Is 7 > 6? Yes!
• This is a better (smaller) successor than 8
• Update ans = 7
• Check if there's an even smaller valid successor in the left subtree
• Move left: root = None (7 has no left child)

Step 5: root = None

• We've reached the end of our search path
• Return ans = 7

Result: The in-order successor of node 6 is node 7.

Notice how we refined our answer from 8 to 7 by continuously searching for the smallest value that's still greater than 6. The algorithm efficiently navigated through only 4 nodes instead of traversing the entire tree.

Solution Implementation

Time and Space Complexity

The time complexity is O(h), where h is the height of the binary search tree. In the worst case, the algorithm traverses from the root to a leaf node, visiting at most h nodes. For a balanced BST, this would be O(log n) where n is the number of nodes, while for a skewed tree it could be O(n).

The space complexity is O(1). The algorithm uses only a constant amount of extra space - just the ans pointer variable to track the potential successor. The iterative approach doesn't use recursion, so there's no additional stack space required.

Common Pitfalls

Pitfall 1: Confusing with Finding Node p First

A common mistake is thinking you need to first locate node p in the tree and then find its successor from that position. This leads to unnecessarily complex code:

Incorrect Approach:

def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
    # First find node p
    current = root
    while current and current.val != p.val:
        if p.val < current.val:
            current = current.left
        else:
            current = current.right
  
    # Then find successor... (more complex logic)

Why this is problematic:

• Requires two separate traversals
• More complex logic to handle different cases after finding p
• Doesn't leverage the BST property efficiently

Solution: The correct approach directly searches for the successor by comparing values with p.val, not by finding p first. We only need p.val to make comparisons, not the actual node position.

Pitfall 2: Incorrect Handling of Equal Values

Some implementations incorrectly handle the case when root.val == p.val:

Incorrect Code:

while root:
    if root.val >= p.val:  # Wrong: includes equal case
        successor = root
        root = root.left
    else:
        root = root.right

Why this fails:

• When root.val == p.val, we save the current node as successor
• This would return p itself as its own successor, which is wrong
• The successor must be strictly greater than p.val

Solution: Always use strict inequality (root.val > p.val) when checking for potential successors. Nodes with values equal to p.val should be treated the same as nodes with smaller values - by moving to the right subtree.

Pitfall 3: Forgetting to Update the Answer Variable

A subtle bug occurs when developers forget to save the potential successor:

Incorrect Code:

while root:
    if root.val > p.val:
        # Forgot to save: ans = root
        root = root.left
    else:
        root = root.right
return ans  # Always returns None

Why this fails:

• Without saving ans = root, we lose track of valid successors
• The function would always return None even when a successor exists

Solution: Always update the answer variable before moving to the left subtree. This ensures we keep track of the smallest valid successor found so far.

Pitfall 4: Misunderstanding When to Go Left vs Right

Some might incorrectly think they should always go right to find a larger value:

Incorrect Logic:

if root.val > p.val:
    ans = root
    root = root.right  # Wrong: should go left to find smaller successor

Why this fails:

• Once we find a node greater than p.val, we need the smallest such node
• Going right would find larger values, not the immediate successor
• This could skip over the actual successor

Solution: Remember the goal: find the smallest value that is still greater than p.val. When you find a candidate (value > p.val), explore left to see if there's a smaller valid candidate. Only go right when the current value is not large enough (≤ p.val).