Code Implementation

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

class Solution:
    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
        successor = None
        while root:
            if p.val < root.val:
                successor = root
                root = root.left
            else:
                root = root.right
        return successor
    

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode* successor = nullptr;
        while (root) {
            if (p->val < root->val) {
                successor = root;
                root = root->left;
            } else {
                root = root->right;
            }
        }
        return successor;
    }
};
    

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode successor = null;
        while (root != null) {
            if (p.val < root.val) {
                successor = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return successor;
    }
}
    

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @return {TreeNode}
 */
var inorderSuccessor = function(root, p) {
    let successor = null;
    while (root) {
        if (p.val < root.val) {
            successor = root;
            root = root.left;
        } else {
            root = root.right;
        }
    }
    return successor;
};
    

Problem Description

Given the root of a binary search tree (BST) and a node p in it, find the node in the BST that has the smallest key greater than p.val (the "inorder successor" of p). If such a node does not exist, return null.

• Each node in the BST has a unique value.
• You are guaranteed that p is a node in the tree.
• The BST property holds: for any node, all nodes in its left subtree have smaller values, all in right have larger.

The goal is to return the next node in the in-order traversal of the BST after p, or null if p is the largest.

Thought Process

To solve this problem, we first recall what "inorder successor" means: in the in-order traversal of a BST, the successor of a node is the next node visited after it. For a BST, this is the node with the smallest value greater than p.val.

The brute-force way would be to perform an in-order traversal, collect all nodes, and then find p in that list and return the next node. But that's inefficient: it traverses the whole tree even if p is near the end.

Instead, we can use the BST property to optimize. Since all values greater than p.val are in the right subtree or above p, we can search efficiently. The key insight is:

• If p has a right child, the successor is the leftmost node in p's right subtree.
• If p has no right child, the successor is one of p's ancestors. Specifically, the lowest ancestor for which p is in the left subtree.

We can find the successor by traversing from the root, updating a candidate successor whenever we move left from a node larger than p.val.

Solution Approach

• Step 1: Start from the root. Initialize a variable successor to null.
• Step 2: While the current node is not null:
  • If p.val is less than the current node's value, this node could be a successor. Set successor to this node and move to the left child (since there could be a closer successor).
  • If p.val is greater than or equal to the current node's value, move to the right child (since all values in the left subtree are too small).
• Step 3: Once you reach a null node, successor (if set) is the answer. If not set, there is no successor.

This approach leverages the BST property, so we never need to visit unnecessary nodes. It's efficient and easy to implement.

Example Walkthrough

Suppose our BST is:

        5
       / \
      3   6
     / \
    2   4
  

Let's find the inorder successor of node p with value 3.

• Start at root (5). Since 3 < 5, set successor to 5, move to left child (3).
• At node 3. 3 == 3, so move to right child (4).
• At node 4. 3 < 4, set successor to 4, move to left child (null).
• We reached null. The latest successor set is 4, so that's our answer.

If we tried with p = 6, we'd never set successor, so we return null.

Time and Space Complexity

• Brute-force approach: In-order traversal visits all nodes, so time complexity is O(N), space complexity is O(N) (for storing nodes).
• Optimized approach (this solution): Each step moves down the tree, so time complexity is O(H), where H is the height of the tree (O(log N) for balanced, O(N) for skewed). Space complexity is O(1) since we use only a few pointers.

Summary

The problem asks for the next node in the in-order traversal of a BST, given a node p. By leveraging the BST property, we can efficiently search for the successor by traversing from the root, updating our candidate whenever we move left. This avoids unnecessary work and results in an elegant and efficient solution, with O(H) time and O(1) space.