BST Inorder Successor in DSA Java - Deep Dive

Overview - BST Inorder Successor

What is it?

A Binary Search Tree (BST) is a tree where each node has at most two children, and the left child's value is less than the parent's, while the right child's value is greater. The inorder successor of a node in a BST is the node that comes immediately after it when the tree is traversed in order (left, root, right). Finding the inorder successor helps in many tasks like deleting nodes or navigating the tree in sorted order.

Why it matters

Without the concept of an inorder successor, it would be hard to move through a BST in sorted order efficiently. This would make operations like finding the next bigger number or deleting nodes more complex and slower. In real life, this affects databases, search engines, and any system that relies on sorted data for quick access.

Where it fits

Before learning this, you should understand what a BST is and how inorder traversal works. After mastering inorder successor, you can learn about BST deletion, balanced trees like AVL or Red-Black trees, and other tree traversal techniques.

Mental Model

Core Idea

The inorder successor of a node in a BST is the next node visited after it in an inorder traversal, which is the smallest node greater than the given node.

Think of it like...

Imagine a line of people sorted by height. The inorder successor of a person is the very next taller person standing right after them in the line.

       20
      /  \
    10    30
      \     \
      15    40

Inorder traversal: 10 -> 15 -> 20 -> 30 -> 40
Inorder successor of 15 is 20
Inorder successor of 20 is 30

Build-Up - 7 Steps

1

Foundation

Understanding BST Structure

Concept: Learn what a BST is and how its nodes are arranged.

A BST is a tree where each node has a value. For any node, all values in its left subtree are smaller, and all values in its right subtree are larger. This property helps in searching efficiently.

Result

You can quickly decide to go left or right when searching for a value.

Understanding the BST property is crucial because it allows us to find the inorder successor by comparing values and navigating the tree.

2

Foundation

Inorder Traversal Basics

Concept: Learn how inorder traversal visits nodes in sorted order.

Inorder traversal means visiting the left child, then the node itself, then the right child recursively. For a BST, this visits nodes from smallest to largest.

Result

The nodes are visited in ascending order of their values.

Knowing inorder traversal order helps us understand what 'next node' means in the context of BST.

3

Intermediate

Finding Successor When Right Child Exists

🤔Before reading on: If a node has a right child, do you think its inorder successor is the right child itself or somewhere else? Commit to your answer.

Concept: If the node has a right child, the successor is the smallest node in that right subtree.

To find the successor when the right child exists, go to the right child, then keep going left until you reach a node with no left child. That node is the successor.

Result

You find the next bigger node in the right subtree.

Understanding this rule leverages the BST property to find the successor efficiently without traversing the whole tree.

4

Intermediate

Finding Successor When No Right Child

🤔Before reading on: If a node has no right child, do you think its successor is above it in the tree or does it not have one? Commit to your answer.

Concept: If the node has no right child, the successor is one of its ancestors, specifically the lowest ancestor whose left child is also an ancestor of the node.

Start from the root and move down the tree. Keep track of the last node where you took a left turn. That node is the successor if no right child exists.

Result

You find the next bigger node by moving up the tree to the correct ancestor.

Knowing how to find the successor without a right child prevents unnecessary traversal and uses the BST structure cleverly.

5

Intermediate

Implementing Inorder Successor in Java

Concept: Combine the two cases into a working Java method.

```java class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; } } public class BSTSuccessor { public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { if (p.right != null) { TreeNode curr = p.right; while (curr.left != null) { curr = curr.left; } return curr; } TreeNode successor = null; TreeNode curr = root; while (curr != null) { if (p.val < curr.val) { successor = curr; curr = curr.left; } else if (p.val > curr.val) { curr = curr.right; } else { break; } } return successor; } } ```

Result

The method returns the inorder successor node or null if none exists.

Implementing both cases in code solidifies understanding and shows how theory translates to practice.

6

Advanced

Handling Edge Cases and Null Successors

🤔Before reading on: Do you think the inorder successor always exists for every node? Commit to yes or no.

Concept: Not every node has an inorder successor; the largest node has none.

If the node is the largest in the BST, it has no successor, so the method returns null. Also, handle cases where the node is not found or the tree is empty.

Result

The method safely returns null when no successor exists, avoiding errors.

Recognizing edge cases prevents bugs and ensures robust code in real applications.

7

Expert

Optimizing Successor Search Without Parent Pointers

🤔Before reading on: Is it possible to find the inorder successor without storing parent pointers? Commit to yes or no.

Concept: You can find the successor without parent pointers by starting from the root each time and using BST properties.

Since nodes don't have parent links, start at the root and traverse down, keeping track of potential successors when moving left. This avoids extra memory but costs O(h) time per query, where h is tree height.

Result

You get a space-efficient method that works even without parent references.

Understanding this tradeoff between space and time is key for designing efficient BST operations in constrained environments.

Under the Hood

The inorder successor relies on the BST property that left children are smaller and right children are larger. When a node has a right subtree, the successor is the smallest node there, found by going left as far as possible. Without a right subtree, the successor is an ancestor node where the path to the current node last turned left. Internally, this means the algorithm uses comparisons to navigate the tree and track potential successors.

Why designed this way?

This approach was designed to leverage the BST's sorted structure for efficient navigation. Alternatives like storing parent pointers increase memory usage, while full inorder traversal is inefficient. The chosen method balances time and space, making it practical for many applications.

Root
  │
  ├─ Left Subtree (values < root)
  │     └─ ...
  ├─ Node p
  │     ├─ Left Child (values < p)
  │     └─ Right Child (values > p)
  └─ Right Subtree (values > root)

Successor search:
If p.right != null -> go right, then left as far as possible
Else -> go up ancestors to find first left turn

Myth Busters - 3 Common Misconceptions

Quick: If a node has a right child, is its inorder successor always that right child? Commit yes or no.

Common Belief: The inorder successor of a node with a right child is always its immediate right child.

Reality: The successor is the leftmost node in the right subtree, which may be deeper than the immediate right child.

Why it matters: Assuming the right child is always the successor leads to incorrect results and bugs in tree navigation.

Quick: Does every node in a BST have an inorder successor? Commit yes or no.

Common Belief: Every node in a BST has an inorder successor.

Reality: The largest node has no inorder successor because no bigger node exists.

Why it matters: Failing to handle this causes null pointer errors or infinite loops in code.

Quick: Can you find the inorder successor without starting from the root if nodes lack parent pointers? Commit yes or no.

Common Belief: You can find the inorder successor by moving up the tree even if nodes don't have parent pointers.

Reality: Without parent pointers, you must start from the root each time to find the successor.

Why it matters: Assuming otherwise leads to inefficient or impossible implementations.

Expert Zone

1

When the BST is unbalanced, the height affects the time complexity of successor search, making it O(h) where h can be as bad as n.

2

In threaded BSTs, successor pointers are stored explicitly, allowing O(1) successor retrieval, which is a specialized optimization.

3

In concurrent BSTs, finding successors requires careful synchronization to avoid race conditions and inconsistent views.

When NOT to use

If you need frequent successor queries and the BST is large and unbalanced, consider balanced trees like AVL or Red-Black trees for guaranteed performance. For constant-time successor access, threaded BSTs or augmented data structures are better.

Production Patterns

In databases and file systems, inorder successor logic helps implement range queries and ordered iteration. It is also used in deletion algorithms where the successor replaces a deleted node to maintain BST properties.

Connections

Inorder Traversal

Builds-on

Understanding inorder traversal is essential because the successor is defined by the order nodes are visited in this traversal.

Tree Deletion in BST

Builds-on

Finding the inorder successor is a key step in deleting nodes with two children, as the successor replaces the deleted node.

Sorted Linked List Navigation

Similar pattern

Navigating to the next element in a sorted linked list is conceptually similar to finding the inorder successor in a BST, both represent moving to the next bigger element.

Common Pitfalls

#1 Assuming the right child is always the inorder successor.

Wrong approach:

if (node.right != null) return node.right;

Correct approach:

if (node.right != null) {
TreeNode curr = node.right;
while (curr.left != null) {
curr = curr.left;
}
return curr;
}

Root cause:

Misunderstanding that the successor is the smallest node in the right subtree, not necessarily the immediate right child.

#2 Not handling the case when the node has no successor (largest node).

Wrong approach:

Always returning a node without checking if successor exists, leading to null pointer exceptions.

Correct approach:

Return null if no successor is found after traversal.

Root cause:

Assuming every node has a successor without considering tree boundaries.

#3 Trying to find successor by moving up without parent pointers.

Wrong approach:

Using parent references that don't exist, causing compilation or runtime errors.

Correct approach:

Start from root and track potential successors while searching for the node.

Root cause:

Not accounting for the absence of parent pointers in the tree structure.

Key Takeaways

The inorder successor of a node in a BST is the next node visited in inorder traversal, representing the next bigger value.

If the node has a right child, the successor is the leftmost node in that right subtree; otherwise, it is an ancestor found by tracking left turns from the root.

Not every node has a successor; the largest node in the BST has none, so code must handle null results safely.

Finding the successor without parent pointers requires starting from the root and using BST properties to track potential successors.

Understanding inorder successor is essential for BST operations like deletion and ordered traversal, impacting many real-world applications.

Practice

1. What is the inorder successor of a node in a Binary Search Tree (BST)?

easy

A. The node with the smallest key greater than the given node's key

B. The node with the largest key smaller than the given node's key

C. The root node of the BST

D. The left child of the given node

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits nodes in ascending order of their keys in a BST.

2. Step 2: Define inorder successor

   The inorder successor of a node is the next node visited after it in inorder traversal, which is the smallest node greater than it.

3. Final Answer:

   The node with the smallest key greater than the given node's key -> Option A

4. Quick Check:

   Inorder successor = smallest greater key [OK]

Hint: Inorder successor is next bigger node in sorted order [OK]

Common Mistakes:

• Confusing successor with predecessor
• Thinking successor is always right child
• Assuming successor is parent node

2. Which of the following Java method signatures correctly represents a function to find the inorder successor in a BST node class?

easy

A. public void inorderSuccessor(Node p)

B. public Node inorderSuccessor(Node root, Node p)

C. public int inorderSuccessor(Node root)

D. public Node inorderSuccessor(int key)

Solution

1. Step 1: Identify required inputs and outputs

   To find inorder successor, we need the BST root and the target node; output is the successor node.

2. Step 2: Match method signature

   public Node inorderSuccessor(Node root, Node p) takes root and node, returns Node, matching requirements.

3. Final Answer:

   public Node inorderSuccessor(Node root, Node p) -> Option B

4. Quick Check:

   Input root and node, output node [OK]

Hint: Method needs root and target node, returns successor node [OK]

Common Mistakes:

• Missing root parameter
• Returning int instead of Node
• Using void return type

3. Given the BST below and the node with value 15, what is the inorder successor?

       20
      /  \
    10    30
      \
      15

medium

A. 20

B. 15

C. 30

D. 10

Solution

1. Step 1: Locate node 15 and check right subtree

   Node 15 has no right child, so successor is ancestor with greater value.

2. Step 2: Find lowest ancestor greater than 15

   Ancestor 20 is the next bigger node after 15.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Next bigger after 15 is 20 [OK]

Hint: If no right child, successor is nearest bigger ancestor [OK]

Common Mistakes:

• Choosing 30 which is too big
• Choosing 10 which is smaller
• Choosing the node itself

4. Consider this buggy Java code snippet to find the inorder successor of a node in BST:

public Node inorderSuccessor(Node root, Node p) {
    if (p.right != null) {
        Node curr = p.right;
        while (curr.left != null) {
            curr = curr.left;
        }
        return curr;
    }
    Node succ = null;
    while (root != null) {
        if (p.val < root.val) {
            succ = root;
            root = root.left;
        } else {
            root = root.right;
        }
    }
    return succ;
}

What is the main bug in this code?

medium

A. It uses wrong comparison operator in while loop

B. It incorrectly updates successor when p.val >= root.val

C. It does not handle the case when p has no right child

D. It may return null even if successor exists

Solution

1. Step 1: Analyze right subtree handling

   If p has right child, code correctly finds leftmost node in right subtree.

2. Step 2: Analyze ancestor search loop

   Loop updates successor when p.val < root.val, else moves right. This is correct logic.

3. Step 3: Identify potential null return

   If p is the largest node, no successor exists, so null return is valid. Otherwise, code works.

4. Final Answer:

   It may return null even if successor exists -> Option D

5. Quick Check:

   Null return possible if logic misses successor [OK]

Hint: Check if successor can be missed when traversing ancestors [OK]

Common Mistakes:

• Assuming null means no successor always
• Ignoring right subtree case
• Misreading comparison operators

5. You have a BST and want to find the inorder successor of node with value 25. The BST is:

        40
       /  \
     20    60
    /  \  /  \
  10  30 50  70
       \
       25

Which node is the inorder successor of 25 and why?

hard

A. 30, because it is the smallest node greater than 25 in the right subtree

B. 50, because it is the leftmost node in the right subtree of 25

C. 40, because 25 has no right child and 40 is the nearest bigger ancestor

D. 20, because it is the parent of 25

Solution

1. Step 1: Check if node 25 has right child

   Node 25 has no right child, so successor is ancestor or next bigger node.

2. Step 2: Find nearest ancestor greater than 25

   Node 40 is the nearest ancestor greater than 25, so it is the inorder successor.

3. Final Answer:

   40, because 25 has no right child and 40 is the nearest bigger ancestor -> Option C

4. Quick Check:

   Next bigger node after 25 is 40 [OK]

Hint: Successor is leftmost node in right subtree or nearest bigger ancestor [OK]

Common Mistakes:

• Choosing 30 which is smaller than 25
• Choosing 50 which is too far
• Choosing parent 20 which is smaller