LeetCode 285: Inorder Successor in BST Solution in Python – A Step-by-Step Guide

What Is LeetCode 285: Inorder Successor in BST?

In LeetCode 285: Inorder Successor in BST, you’re given the root of a binary search tree and a node p within it. Your task is to return the node that’s the inorder successor of p—the next node in an inorder traversal—or None if p is the last node. In a BST, inorder traversal gives nodes in ascending order, so the successor is the next larger value. For example, in a tree with values [2, 1, 3], if p is 1, the successor is 2. This problem tests your understanding of BST properties and traversal, sharing a spirit with challenges like LeetCode 94: Binary Tree Inorder Traversal.

Problem Statement

• Input: Root of a BST and a node p in the tree.
• Output: The inorder successor node of p, or None if none exists.
• Rules: BST properties hold (left < root < right); use inorder order; assume unique values.

Constraints

• Tree nodes: 1 to 10⁴ (10,000).
• Node values: -10⁵ to 10⁵.
• p is a valid node in the tree.

Examples

• Input: Root = [2, 1, 3], p = 1
• Inorder: [1, 2, 3]
• Output: Node with value 2
• Input: Root = [5, 3, 6, 2, 4, null, null, 1], p = 6
• Inorder: [1, 2, 3, 4, 5, 6]
• Output: None (6 is last)
• Input: Root = [5, 3, 6, 2, 4], p = 4
• Inorder: [2, 3, 4, 5, 6]
• Output: Node with value 5

Understanding the Problem: Finding the Next in Line

To solve LeetCode 285: Inorder Successor in BST in Python, we need to find the node that follows p in an inorder traversal of the BST. Inorder means visiting left subtree, root, then right subtree, which in a BST gives us ascending order. For a node p, its successor is either:

• The leftmost node in its right subtree (if it has one), or
• An ancestor we encounter while moving up (if no right child, and only if p was in a left subtree).

We’ll use: 1. Best Solution (Iterative Traversal): O(h) time (h = tree height), O(1) space—fast and lean. 2. Alternative Solution (Recursive Traversal): O(h) time, O(h) space—clear but uses stack space.

Let’s dive into the iterative solution with a beginner-friendly walkthrough.

Best Solution: Iterative Traversal

Why This Is the Best Solution

The iterative traversal is the top choice for LeetCode 285 because it’s efficient—O(h) time, where h is the tree height (often much less than n)—and uses O(1) space, avoiding recursion overhead. It leverages BST properties to walk down the tree, keeping track of the potential successor without storing the full traversal. For beginners, it’s like following a treasure map with just a compass—no need for a big backpack!

How It Works

Picture this as a guided hike through the BST: you start at the root, head toward p, and keep an eye out for the next bigger value. Since it’s a BST, we can use the value of p to navigate efficiently:

• Step 1: Traverse Down:
• Start at the root with a successor variable (initially None).
• Move left if p.val is less than the current node, right if greater.
• Step 2: Track Successor:
• When moving left, the current node could be the successor (it’s bigger than p), so update successor.
• When moving right, no update—successor stays as is (we’re past potential candidates).
• Step 3: Stop at p:
• When you reach p, check its right subtree:
• If it exists, the successor is the leftmost node there.
• If not, use the tracked successor.
• Step 4: Why It Works:
• BST ensures inorder order aligns with value order.
• Moving left updates the successor; moving right skips it.
• Right subtree check handles the “next in line” case.

It’s like finding the next bus stop by checking the route and the next turn!

Step-by-Step Example

Example: Root = [5, 3, 6, 2, 4], p = 4

• Inorder: [2, 3, 4, 5, 6].
• Start: root = 5, successor = None.
• Traverse:
• 5 > 4: Go left to 3, successor = 5.
• 3 < 4: Go right to 4, successor = 5.
• Found 4: Check right subtree (None), use successor.
• Result: Node 5.

Example: Root = [2, 1, 3], p = 1

• Inorder: [1, 2, 3].
• Start: root = 2, successor = None.
• Traverse:
• 2 > 1: Go left to 1, successor = 2.
• Found 1: Right subtree = None, use successor.
• Result: Node 2.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained simply:

Copy code# 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
        curr = root

        # Step 1: Find p and track potential successor
        while curr and curr.val != p.val:
            if p.val < curr.val:
                successor = curr  # Could be successor if p is in left
                curr = curr.left
            else:
                curr = curr.right  # No successor update

        # Step 2: If p found, check right subtree
        if curr:
            if curr.right:
                # Find leftmost in right subtree
                curr = curr.right
                while curr.left:
                    curr = curr.left
                return curr
            return successor

        return None  # p not found (shouldn’t happen per problem)

• Line 11-12: successor tracks the potential next node; curr starts at root.
• Line 14-19: Loop until curr is p:
• If p.val < curr.val, update successor and go left.
• Else, go right (no successor update).
• Line 21-28: If curr is p:
• If right child exists, successor is leftmost node there.
• Else, use tracked successor.
• Line 30: Fallback (assumes p is in tree).

• Time Complexity: O(h)—height of tree, often log n in balanced BST.
• Space Complexity: O(1)—no recursion or extra storage.

This solution is like a swift BST hike—straight to the point!

Alternative Solution: Recursive Traversal

Why an Alternative Approach?

The recursive method uses inorder traversal to list all nodes, then finds p’s successor—O(h) time but O(h) space due to the call stack. It’s intuitive, like writing down the inorder sequence and picking the next one, making it a great learning tool for beginners.

How It Works

Imagine unrolling the BST into a sorted list via inorder traversal, then finding p and the next node:

• Step 1: Traverse recursively, tracking the previous node.
• Step 2: When p is found, the next visited node is the successor.
• Step 3: Return it when identified.

It’s like following a guidebook through the tree!

Step-by-Step Example

Example: Root = [5, 3, 6, 2, 4], p = 4

• Inorder: [2, 3, 4, 5, 6].
• Traverse:
• Left to 3, then 2 (prev=2), 3 (prev=3), 4 (prev=4, found p).
• Next is 5 → successor.
• Result: Node 5.

Code for Recursive Approach

Copy codeclass Solution:
    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
        self.prev = None
        self.successor = None

        def inorder(node):
            if not node or self.successor:
                return
            inorder(node.left)
            if self.prev == p:
                self.successor = node
            self.prev = node
            inorder(node.right)

        inorder(root)
        return self.successor

• Time Complexity: O(h)—visits nodes up to successor.
• Space Complexity: O(h)—recursion stack.

It’s clear but heavier.

Comparing the Two Solutions

• Iterative (Best):
• Pros: O(h) time, O(1) space, direct.
• Cons: Slightly less intuitive.
• Recursive (Alternative):
• Pros: O(h) time, follows inorder naturally.
• Cons: O(h) space, recursion overhead.

Iterative wins for efficiency.

Additional Examples and Edge Cases

• Root = [1], p = 1: No successor → None.
• Root = [2, 1], p = 2: No successor → None.
• Root = [3, 1, 4, null, 2], p = 2: Successor = 3.

Both handle these well.

Complexity Breakdown

• Iterative: Time O(h), Space O(1).
• Recursive: Time O(h), Space O(h).

Iterative is the lean choice.

Key Takeaways

• Iterative: Use BST properties—fast!
• Recursive: Follow inorder—clear!
• BST: Order is your friend.
• Python Tip: Trees and loops rock—see [Python Basics](/python/basics).

Final Thoughts: Succeed in BST

LeetCode 285: Inorder Successor in BST in Python is a neat tree challenge. Iterative traversal keeps it swift and light, while recursive offers a beginner-friendly path. Want more? Try LeetCode 94: Binary Tree Inorder Traversal or LeetCode 450: Delete Node in a BST. Ready to climb? Head to Solve LeetCode 285 on LeetCode and find that successor today!