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

What Is LeetCode 510: Inorder Successor in BST II?

In LeetCode 510: Inorder Successor in BST II, you’re given a node in a BST where each node has a value, left and right children, and a parent pointer (except the root). Your task is to find the inorder successor—the next node in an inorder traversal (left, root, right). In a BST, this is the next larger value. For example, in a tree with values [2, 1, 3], the successor of 1 is 2. This problem builds on LeetCode 285: Inorder Successor in BST, but uses parent pointers instead of root access.

Problem Statement

• Input: A Node object with val, left, right, and parent attributes.
• Output: The successor Node or None if none exists.
• Rules: BST properties hold (left < root < right); inorder successor is next in sorted order.

Constraints

• Number of nodes: 1 to 10⁴.
• Node values: -10⁵ to 10⁵.
• All values are unique.
• Input node is not null and exists in the tree.

Examples

• Input: Tree [2,1,3], node = 1
• Output: Node with value 2
• Inorder: 1, 2, 3 → successor of 1 is 2.
• Input: Tree [5,3,6,2,4,null,null,1], node = 6
• Output: None
• Inorder: 1, 2, 3, 4, 5, 6 → 6 is last.
• Input: Tree [5,3,6,2,4,null,null,1], node = 4
• Output: Node with value 5
• Inorder: 1, 2, 3, 4, 5, 6 → successor of 4 is 5.

Understanding the Problem: Finding the Next in Line

To solve LeetCode 510: Inorder Successor in BST II in Python, we need a function that finds the inorder successor of a given node in a BST using its parent pointer. Inorder traversal of a BST gives nodes in ascending order, so the successor is the next larger value. With parent pointers, we don’t need the root, but we must handle two cases: nodes with right children and nodes without. We’ll explore:

• Best Solution (Parent Pointers): O(h) time, O(1) space—fast and space-efficient.
• Alternative Solution (Recursive Inorder): O(n) time, O(n) space—simpler but less tailored.

Let’s dive into the parent pointer solution with a friendly breakdown!

Best Solution: Using Parent Pointers with O(h) Time

Why Parent Pointers Win

The parent pointer approach is the best for LeetCode 510 because it leverages the BST structure and parent links for an O(h) time complexity (h is tree height) and O(1) space. It avoids traversing the entire tree by directly finding the successor based on two scenarios: going down the right subtree or up via parents. It’s like having a map that points you to the next stop without wandering!

How It Works

Think of this as a BST road trip:

• Step 1: Check Right Child:
• If the node has a right child, the successor is the leftmost node in the right subtree (smallest value there).
• Step 2: Go Up via Parents:
• If no right child, move up to the parent:
• If you came from the left, the parent is the successor.
• If from the right, keep going up until you came from the left or hit null.
• Step 3: Return:
• Return the successor node or None if at the end.
• Why It Works:
• BST inorder: left, root, right.
• Right subtree’s leftmost is next; parent rules handle no-right cases.

It’s like a smart BST navigator!

Step-by-Step Example

Example: Tree [5,3,6,2,4,null,null,1], node = 4

• Tree:
``` 5 / \ 3 6 / \ 2 4 / 1 ```
• Inorder: 1, 2, 3, 4, 5, 6.
• Node: 4.
• Step 1: 4 has no right child.
• Step 2: Go up:
• Parent = 3, 4 was right child, go up.
• Parent = 5, 3 was left child, stop.
• Step 3: Successor = 5.
• Result: Node with value 5.

Example: Node = 6

• Step 1: 6 has no right child.
• Step 2: Parent = 5, 6 was right child, go up.
• Parent = None (root), stop.
• Result: None.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass 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':
        # Step 1: If right child exists, find leftmost in right subtree
        if node.right:
            curr = node.right
            while curr.left:
                curr = curr.left
            return curr

        # Step 2: No right child, go up via parents
        curr = node
        while curr.parent and curr == curr.parent.right:
            curr = curr.parent

        # Step 3: Return parent (if came from left) or None
        return curr.parent

• Lines 10-14: If right child exists:
• Start at right child.
• Go left as far as possible (smallest in right subtree).
• Return that node.
• Lines 17-19: No right child:
• Start at node, go up while you’re a right child.
• Line 22: Return parent (successor if came from left) or None.
• Time Complexity: O(h)—height of tree (h ≤ n).
• Space Complexity: O(1)—no extra space.

It’s like a BST successor GPS!

Alternative Solution: Recursive Inorder Traversal

Why an Alternative Approach?

The recursive inorder traversal finds the successor by traversing the entire tree to build the inorder sequence, then locating the next value. It’s O(n) time and O(n) space—simpler if you’re used to standard traversals, but less efficient here since we have parent pointers and don’t need the full tree.

How It Works

Picture this as a full tree tour:

• Step 1: Find the root (go up to null parent).
• Step 2: Perform inorder traversal, storing nodes.
• Step 3: Find the node’s index, return next node or None.

It’s like mapping the whole route!

Step-by-Step Example

Example: Tree [2,1,3], node = 1

• Tree:
``` 2 / \ 1 3 ```
• Step 1: Root = 2 (node 1’s parent, parent’s parent = None).
• Step 2: Inorder: [1, 2, 3].
• Step 3: Node 1 at index 0, successor at 1 = 2.
• Result: Node with value 2.

Code for Recursive Approach

Copy codeclass Solution:
    def inorderSuccessor(self, node: 'Node') -> 'Node':
        # Step 1: Find root
        root = node
        while root.parent:
            root = root.parent

        # Step 2: Inorder traversal
        nodes = []
        def inorder(curr):
            if not curr:
                return
            inorder(curr.left)
            nodes.append(curr)
            inorder(curr.right)

        inorder(root)

        # Step 3: Find successor
        for i in range(len(nodes)):
            if nodes[i] == node and i + 1 < len(nodes):
                return nodes[i + 1]
        return None

• Lines 4-6: Climb to root.
• Lines 9-15: Inorder traversal to list nodes.
• Lines 18-20: Find node, return next or None.
• Time Complexity: O(n)—full traversal.
• Space Complexity: O(n)—node list.

It’s a full-tree explorer!

Comparing the Two Solutions

• Parent Pointers (Best):
• Pros: O(h) time, O(1) space, uses problem setup.
• Cons: Parent logic.
• Recursive Inorder (Alternative):
• Pros: O(n) time, familiar traversal.
• Cons: O(n) space, overkill.

Parent pointers win for efficiency!

Additional Examples and Edge Cases

• [1]: Node 1 → None.
• [3,1], node = 3: None.
• [5,3,6], node = 3: Node 5.

Parent pointers handle them all!

Complexity Recap

• Parent Pointers: Time O(h), Space O(1).
• Recursive: Time O(n), Space O(n).

Parent pointers are the BST star!

Key Takeaways

• Parent Pointers: Smart navigation—learn at Python Basics!
• BST: Inorder = sorted.
• Successor: Right or up.
• Python: Pointers simplify!

Final Thoughts: Find the Next Node!

LeetCode 510: Inorder Successor in BST II in Python is a clever BST challenge. Parent pointers make it fast, while recursive inorder keeps it classic. Want more? Try LeetCode 285: Inorder Successor in BST or LeetCode 98: Validate BST. Ready to traverse? Head to Solve LeetCode 510 on LeetCode and find that successor today!