BST Inorder Successor in DSA C#

Mental Model

The inorder successor of a node in a BST is the next node you visit in an inorder traversal, which means the smallest node bigger than the given node.

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

      5
     / \
    3   7
   / \   \
  2   4   8

Node: 3 ↑
Inorder successor: 4

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, find inorder successor of node 3

Goal: Find the node that comes right after 3 in inorder traversal

Step 1: Check if node 3 has a right child

Node 3 -> right child 4
Tree unchanged

Why: If right child exists, successor is the leftmost node in right subtree

Step 2: Go to right child 4 and check for left children

Node 4 -> no left child
Tree unchanged

Why: Leftmost node in right subtree is 4 itself

Step 3: Return node 4 as inorder successor

Successor found: 4

Why: 4 is the smallest node bigger than 3

Result:

4

Annotated Code

DSA C#

using System;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

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; // advance to leftmost node in right subtree
            }
            return curr; // successor found in right subtree
        }
        TreeNode successor = null;
        TreeNode currNode = root;
        while (currNode != null) {
            if (p.val < currNode.val) {
                successor = currNode; // potential successor
                currNode = currNode.left; // go left to find smaller successor
            } else {
                currNode = currNode.right; // go right to find node p
            }
        }
        return successor; // successor found or null if none
    }

    public static void Main() {
        TreeNode root = new TreeNode(5,
            new TreeNode(3,
                new TreeNode(2),
                new TreeNode(4)),
            new TreeNode(7,
                null,
                new TreeNode(8)));
        TreeNode p = root.left; // node with value 3
        BSTSuccessor bst = new BSTSuccessor();
        TreeNode succ = bst.InorderSuccessor(root, p);
        Console.WriteLine(succ != null ? succ.val.ToString() : "null");
    }
}

if (p.right != null) {

Check if node has right subtree to find successor there

curr = curr.left;

Move to leftmost node in right subtree for smallest bigger value

return curr;

Return successor found in right subtree

while (currNode != null) {

Traverse from root to find successor if no right subtree

if (p.val < currNode.val) {

If current node is bigger, it can be successor; go left to find smaller one

successor = currNode;

Update potential successor

currNode = currNode.left;

Go left to find closer successor

currNode = currNode.right;

Go right if current node is smaller or equal to p

return successor;

Return found successor or null if none

Output

4

Complexity Analysis

Time: O(h) because we traverse down the tree height h at most once

Space: O(1) because we use only a few pointers, no extra data structures

vs Alternative: Naive inorder traversal takes O(n) time; this method uses BST properties to find successor faster

Edge Cases

Node has no right child and is the largest node

Returns null because no successor exists

DSA C#

return successor;

Node has right child with multiple left descendants

Returns leftmost node in right subtree as successor

DSA C#

while (curr.left != null) { curr = curr.left; }

Node is root with no left subtree

Finds successor by traversing from root to find smallest bigger node

DSA C#

while (currNode != null) { ... }

When to Use This Pattern

When asked to find the next bigger node in a BST, use the inorder successor pattern because it leverages BST order to find the answer efficiently.

Common Mistakes

Mistake: Only checking right subtree and ignoring the case when no right child exists
Fix: Add traversal from root to find the lowest ancestor bigger than the node

Mistake: Not moving to the leftmost node in the right subtree when right child exists
Fix: Traverse left children from right child to find smallest bigger node

Summary

Finds the next node in BST inorder traversal after a given node.

Use when you need the smallest node bigger than a given node in a BST.

If right child exists, successor is leftmost node in right subtree; otherwise, find lowest ancestor bigger than node.

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