BST Inorder Successor in DSA C# - Deep Dive

Overview - BST Inorder Successor

What is it?

A Binary Search Tree (BST) Inorder Successor is the node that comes immediately after a given node when the tree is traversed in order (left, root, right). It helps find the next bigger value in the tree. This concept is useful for many tree operations like deletion or finding ranges. Understanding it means knowing how nodes relate in sorted order.

Why it matters

Without knowing the inorder successor, it would be hard to move through a BST in sorted order efficiently. Many algorithms rely on quickly finding the next bigger element, such as in database indexing or autocomplete systems. Without this, operations would be slower and more complex, making software less responsive and efficient.

Where it fits

Before learning this, you should understand what a Binary Search Tree is and how inorder traversal works. After this, you can learn about BST deletion, balanced trees like AVL or Red-Black trees, and advanced tree queries.

Mental Model

Core Idea

The inorder successor of a node in a BST is the smallest node that is bigger than the given node.

Think of it like...

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

       20
      /  \
    10    30
      \     \
      15    40

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

Build-Up - 7 Steps

1

Foundation

Understanding BST and Inorder Traversal

Concept: Learn what a BST is and how inorder traversal visits nodes in sorted order.

A Binary Search Tree is a tree where left child nodes are smaller and right child nodes are bigger than the parent. Inorder traversal visits nodes by going left subtree, then node, then right subtree. This produces sorted values.

Result

Visiting nodes in inorder gives sorted values: for example, 10 -> 15 -> 20 -> 30 -> 40.

Understanding inorder traversal is key because the successor is defined by this sorted order.

2

Foundation

Defining Inorder Successor Concept

Concept: The inorder successor is the next node visited after the current node in inorder traversal.

If you list nodes in sorted order, the successor of a node is the next node in that list. For the largest node, there is no successor.

Result

For node 15, successor is 20; for node 40, successor is null (no next bigger node).

Knowing the successor is about position in sorted order helps us find it logically.

3

Intermediate

Finding Successor When Right Subtree Exists

🤔Before reading on: If a node has a right child, do you think its successor is in the right subtree 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, go to the right child, then keep going left until no more left child exists. That node is the successor.

Result

For node 20, right child is 30; leftmost in right subtree is 30 itself, so successor is 30.

Understanding this rule simplifies finding successors when right subtree exists.

4

Intermediate

Finding Successor When No Right Subtree

🤔Before reading on: If a node has no right child, do you think its successor is a child or an ancestor? Commit to your answer.

Concept: If no right child, successor is the nearest ancestor for which the node is in the left subtree.

Move up the tree using parent links until you find a node that is a left child of its parent. That parent is the successor.

Result

For node 15, no right child; its parent 10 is left child of 20, so successor is 20.

Knowing to look upwards in the tree when no right subtree exists completes the successor search.

5

Intermediate

Implementing Successor Search in Code

Concept: Combine both cases into a function that finds the inorder successor given a node.

```csharp class Node { public int val; public Node left, right, parent; public Node(int v) { val = v; } } Node InorderSuccessor(Node node) { if (node.right != null) { Node curr = node.right; while (curr.left != null) curr = curr.left; return curr; } Node currParent = node.parent; while (currParent != null && node == currParent.right) { node = currParent; currParent = currParent.parent; } return currParent; } ```

Result

Calling InorderSuccessor on node 15 returns node 20; on node 40 returns null.

Seeing the full code clarifies how the two cases work together in practice.

6

Advanced

Handling BST Without Parent Pointers

🤔Before reading on: Without parent links, do you think you can find the successor by only looking down the tree? Commit to your answer.

Concept: Without parent pointers, you must start from the root and search for the successor by comparing values.

Start at root. If node's value is less than root's, root could be successor; go left. Else go right. Keep track of potential successor. When you reach the node, return last recorded successor.

Result

This method finds successor without parent links but requires root access and extra comparisons.

Knowing this method is important because many BST implementations do not store parent pointers.

7

Expert

Successor in Unbalanced and Balanced BSTs

🤔Before reading on: Do you think balancing the BST changes how successor is found? Commit to your answer.

Concept: Balancing affects tree height but not the successor logic; however, balanced trees guarantee faster successor search.

Balanced BSTs like AVL or Red-Black trees keep height low, so successor search is O(log n). Unbalanced trees can degrade to O(n). The algorithm remains the same but performance differs.

Result

Balanced trees make successor queries efficient even in large datasets.

Understanding performance impact of tree shape on successor search helps in choosing data structures.

Under the Hood

The inorder successor is found by exploiting BST properties: left subtree nodes are smaller, right subtree nodes are bigger. When a right subtree exists, the successor is the smallest node there. Otherwise, the successor is an ancestor node where the current node lies in its left subtree. Parent pointers or root-based search help navigate upwards or from root.

Why designed this way?

This design leverages BST ordering to avoid full traversal. Parent pointers simplify upward navigation but increase memory. Without them, root-based search trades space for time. The approach balances efficiency and simplicity, avoiding scanning the entire tree.

          ┌─────────────┐
          │   Start at   │
          │   given node │
          └──────┬──────┘
                 │
        ┌────────┴────────┐
        │                 │
  Has right child?     No right child
        │                 │
        ▼                 ▼
Go right once,     Move up using parent
then left as far  until node is left child
as possible       of parent; return that parent
        │                 │
        ▼                 ▼
   Return node       Return ancestor or null

Myth Busters - 3 Common Misconceptions

Quick: Is the inorder successor always the right child of the node? Commit yes or no.

Common Belief: The inorder successor is always the right child of the node.

Reality: The successor is the leftmost node in the right subtree if it exists; otherwise, it is an ancestor node, not necessarily the right child.

Why it matters: Assuming successor is always right child causes wrong results when right subtree is missing, leading to bugs in tree operations.

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

Common Belief: If no right child, the successor is always the parent node.

Reality: The successor is the nearest ancestor for which the node is in the left subtree, which may be higher than the immediate parent.

Why it matters: Mistaking immediate parent as successor causes incorrect traversal and errors in algorithms like deletion.

Quick: Does the largest 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 case leads to null reference errors or infinite loops.

Expert Zone

1

In BSTs without parent pointers, successor search requires starting from root and tracking potential successors, which is less intuitive but memory efficient.

2

In threaded BSTs, successor pointers are stored explicitly to speed up inorder traversal without recursion or stacks.

3

Balancing the BST does not change successor logic but ensures worst-case time complexity remains logarithmic.

When NOT to use

If the BST is very unbalanced or degenerated into a linked list, successor search can be slow; in such cases, balanced trees like AVL or Red-Black trees are better. For very large datasets, B-Trees or other disk-friendly structures are preferred.

Production Patterns

In databases and file systems, inorder successor logic is used to navigate indexes efficiently. Balanced BSTs with parent pointers or threaded pointers are common to optimize traversal and updates. Successor search is also key in implementing iterators over sorted data.

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 critical in deletion algorithms to replace a node with its next bigger value, maintaining BST properties.

Linked List Next Pointer

Similar pattern

The inorder successor acts like a 'next' pointer in a linked list, connecting nodes in sorted order, showing how trees can be traversed like lists.

Common Pitfalls

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

Wrong approach:

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

Correct approach:

if (node.right != null) {
Node curr = node.right;
while (curr.left != null) curr = curr.left;
return curr;
} else {
Node currParent = node.parent;
while (currParent != null && node == currParent.right) {
node = currParent;
currParent = currParent.parent;
}
return currParent;
}

Root cause:

Misunderstanding that successor depends on the smallest node in right subtree or ancestor, not just immediate right child.

#2 Using parent pointer incorrectly when node is right child.

Wrong approach:

return node.parent; // always returns immediate parent regardless of position

Correct approach:

Node currParent = node.parent;
while (currParent != null && node == currParent.right) {
node = currParent;
currParent = currParent.parent;
}
return currParent;

Root cause:

Ignoring that successor is the ancestor where node lies in left subtree, not just immediate parent.

#3 Not handling null successor for largest node.

Wrong approach:

Node succ = InorderSuccessor(largestNode);
Console.WriteLine(succ.val); // causes null reference exception

Correct approach:

Node succ = InorderSuccessor(largestNode);
if (succ != null) Console.WriteLine(succ.val); else Console.WriteLine("No successor");

Root cause:

Failing to check for null when no successor exists.

Key Takeaways

The inorder successor is the next bigger node in a BST's sorted order.

If a node has a right subtree, the successor is the leftmost node there.

If no right subtree, the successor is the nearest ancestor where the node is in the left subtree.

Parent pointers simplify successor search, but without them, root-based search is needed.

Balanced BSTs guarantee efficient successor search, while unbalanced trees may degrade performance.

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 key greater than the node's key.

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 C# method signatures correctly represents a function to find the inorder successor of a BST node?

easy

A. public void InorderSuccessor(TreeNode root, TreeNode p)

B. public TreeNode InorderSuccessor(TreeNode root, TreeNode p)

C. public TreeNode FindSuccessor(TreeNode p)

D. public int InorderSuccessor(int root, int p)

Solution

1. Step 1: Check parameter types for BST nodes

   The method should accept the BST root and the target node to find successor, both as TreeNode objects.

2. Step 2: Check return type

   The method returns the successor node, so return type must be TreeNode, not int or void.

3. Final Answer:

   public TreeNode InorderSuccessor(TreeNode root, TreeNode p) -> Option B

4. Quick Check:

   Correct signature uses TreeNode parameters and returns TreeNode [OK]

Hint: Successor method needs root and target node, returns TreeNode [OK]

Common Mistakes:

• Using int instead of TreeNode for parameters
• Returning void instead of TreeNode
• Missing root parameter

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

        20
       /  \
     10    30
       \     \
       15    40

TreeNode successor = InorderSuccessor(root, node15); Console.WriteLine(successor.val);

medium

A. 40

B. 30

C. 20

D. 15

Solution

1. Step 1: Locate node 15 and find its inorder successor

   Node 15 has no right child, so successor is the lowest ancestor whose left child is also ancestor of 15, which is 20.

2. Step 2: Confirm successor value

   20 is the next bigger node after 15 in inorder traversal.

3. Final Answer:

   20 -> Option C

4. Quick Check:

   Successor of 15 is 20 [OK]

Hint: If no right child, go up to first bigger ancestor [OK]

Common Mistakes:

• Choosing right child 30 incorrectly
• Choosing node itself as successor
• Choosing 40 which is too far

4. The following code attempts to find the inorder successor of a node in a BST but returns null incorrectly. What is the bug?

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;
    while (root != null) {
        if (p.val < root.val) {
            successor = root;
            root = root.left;
        } else {
            root = root.right;
        }
    }
    return successor;
}

medium

A. The code does not handle the case when p has no right child

B. The while loop condition should be curr.right instead of curr.left

C. The comparison p.val < root.val should be p.val <= root.val

D. The code is correct and should not return null incorrectly

Solution

1. Step 1: Analyze right subtree handling

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

2. Step 2: Analyze ancestor traversal

   If no right child, code moves up tree to find first ancestor greater than p, correctly updating successor.

3. Step 3: Confirm no logical errors

   Comparisons and loops are correct; code returns null only if no successor exists (p is max node).

4. Final Answer:

   The code is correct and should not return null incorrectly -> Option D

5. Quick Check:

   Code handles both cases correctly [OK]

Hint: Check both right subtree and ancestor paths for successor [OK]

Common Mistakes:

• Changing left to right in while loop incorrectly
• Using <= instead of < causing wrong ancestor selection
• Assuming code misses no-right-child case

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

          40
         /  \
       20    60
      /  \     \
    10   30    70
                 \
                 80

If the node with value 50 does not exist in the tree, what should your inorder successor function return?

hard

A. null, because the node is not in the BST

B. The smallest node greater than 50, which is 60

C. The largest node smaller than 50, which is 40

D. The root node, which is 40

Solution

1. Step 1: Confirm node presence in BST

   Node with value 50 is not present in the BST, so no direct successor can be found.

2. Step 2: Understand successor function behavior

   Successor function requires the node to find its successor; if node not found, function should return null or indicate absence.

3. Final Answer:

   null, because the node is not in the BST -> Option A

4. Quick Check:

   Node missing means no successor found [OK]

Hint: Successor only valid if node exists in BST [OK]

Common Mistakes:

• Returning closest bigger node even if node missing
• Returning root node incorrectly
• Returning predecessor instead of null