NUHMAN.com

Introduction

LeetCode 285: Inorder Successor in BST is a classic problem where you need to find the inorder successor of a given node in a binary search tree (BST). The inorder successor of a node is the node with the smallest key greater than the current node's key.

This problem is often asked in interviews to test your understanding of binary search trees, inorder traversal, and tree structure properties.

Problem Statement

Given a binary search tree and a node in the tree, return the inorder successor of that node in the BST.

• The inorder successor of a node is the next node in inorder traversal.
• If the given node has no inorder successor (i.e., it is the largest node), return None.
• You may assume that the given node is not null.

Example

python

Input:
    2
   / \
  1   3
Target = 1

Output: 2

Explanation: The inorder traversal of the tree is [1, 2, 3]. The successor of 1 is 2.

✅ Step-by-Step Solution

🧠 Intuition

To find the inorder successor of a node, consider the following possibilities:

1. If the node has a right child:

• The inorder successor is the leftmost node in the right subtree. This is because the smallest node greater than the current node will be the leftmost node in the right subtree.

1. If the node doesn't have a right child:

• The inorder successor is one of the ancestors of the node. Specifically, it's the lowest ancestor whose left child is also an ancestor of the node.

✅ Approach

• Case 1: Node has a right child
• Move to the right child and keep going left until you reach the leftmost node.
• Case 2: Node has no right child
• Traverse up the tree using parent pointers or recursively to find the ancestor where the node is in the left subtree (that ancestor is the successor).

✅ Python Code

python

class TreeNode:
    def __init__(self, val=0, left=None, right=None, parent=None):
        self.val = val
        self.left = left
        self.right = right
        self.parent = parent

class Solution:
    def inorderSuccessor(self, node: TreeNode) -> TreeNode:
        if node.right:
            # Case 1: Node has a right child
            node = node.right
            while node.left:
                node = node.left
            return node
        
        # Case 2: Node has no right child, go up the tree
        while node.parent and node.parent.right == node:
            node = node.parent
        return node.parent

🧪 Dry Run Example

Consider this example:

python

        5
       / \
      3   8
     / \
    2   4
Target = 3

• node = 3
• node.right = 4, which has no left child.
• Return node.right (4), as it’s the next node in inorder traversal.

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(h), where h is the height of the treeSpace ComplexityO(1) (we’re only using constant extra space)

• Case 1 (Right child exists): Traverse down to the leftmost node of the right subtree.
• Case 2 (No right child): Traverse up the tree.

🔍 Edge Cases

• No right child: The successor must be an ancestor.
• No ancestor with left child: The node is the largest node in the tree, so the successor is None.
• Single-node tree: The node has no successor.

✅ Conclusion

LeetCode 285: Inorder Successor in BST is an excellent problem for testing your knowledge of binary search trees and tree traversal algorithms. You need to consider:

• Subtree traversal when a right child exists
• Parent relationships when there is no right child

This problem can be extended or modified in various ways, such as finding the inorder predecessor or handling a BST without parent pointers.