BST Inorder Successor in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find the inorder successor of a node in BST

What is the output of the following C# code that finds the inorder successor of a node with value 15 in the BST?

DSA C#

using System;

class Node {
    public int val;
    public Node left, right;
    public Node(int v) { val = v; left = right = null; }
}

class BST {
    public Node root;

    public Node Insert(Node root, int val) {
        if (root == null) return new Node(val);
        if (val < root.val) root.left = Insert(root.left, val);
        else root.right = Insert(root.right, val);
        return root;
    }

    public Node MinValueNode(Node node) {
        Node current = node;
        while (current.left != null) current = current.left;
        return current;
    }

    public Node InorderSuccessor(Node root, Node n) {
        if (n.right != null) return MinValueNode(n.right);
        Node succ = null;
        while (root != null) {
            if (n.val < root.val) {
                succ = root;
                root = root.left;
            } else if (n.val > root.val) {
                root = root.right;
            } else break;
        }
        return succ;
    }
}

class Program {
    static void Main() {
        BST tree = new BST();
        int[] values = {20, 8, 22, 4, 12, 10, 14, 15};
        foreach (int v in values) tree.root = tree.Insert(tree.root, v);
        Node node = new Node(15); // Node to find successor for
        Node succ = tree.InorderSuccessor(tree.root, node);
        Console.WriteLine(succ != null ? succ.val.ToString() : "null");
    }
}

A 8

B 22

C 20

D null

💡 Hint

Remember, if the node has a right child, the successor is the minimum value in the right subtree.

The node with value 15 has no right child. So we look for the lowest ancestor for which 15 is in the left subtree. That ancestor is 20, so the inorder successor is 20.

❓ Predict Output

intermediate

Inorder successor when node has right subtree

What will be printed by this C# code that finds the inorder successor of node with value 8 in the BST?

DSA C#

using System;

class Node {
    public int val;
    public Node left, right;
    public Node(int v) { val = v; left = right = null; }
}

class BST {
    public Node root;

    public Node Insert(Node root, int val) {
        if (root == null) return new Node(val);
        if (val < root.val) root.left = Insert(root.left, val);
        else root.right = Insert(root.right, val);
        return root;
    }

    public Node MinValueNode(Node node) {
        Node current = node;
        while (current.left != null) current = current.left;
        return current;
    }

    public Node InorderSuccessor(Node root, Node n) {
        if (n.right != null) return MinValueNode(n.right);
        Node succ = null;
        while (root != null) {
            if (n.val < root.val) {
                succ = root;
                root = root.left;
            } else if (n.val > root.val) {
                root = root.right;
            } else break;
        }
        return succ;
    }
}

class Program {
    static void Main() {
        BST tree = new BST();
        int[] values = {20, 8, 22, 4, 12, 10, 14};
        foreach (int v in values) tree.root = tree.Insert(tree.root, v);
        Node node = new Node(8); // Node to find successor for
        Node succ = tree.InorderSuccessor(tree.root, node);
        Console.WriteLine(succ != null ? succ.val.ToString() : "null");
    }
}

A 12

B 10

C 14

D 20

💡 Hint

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

Node 8 has a right subtree with nodes 10, 12, 14. The smallest node there is 10, so the inorder successor is 10.

🔧 Debug

advanced

Identify the error in inorder successor code

What error will this C# code produce when trying to find the inorder successor of node 10?

DSA C#

using System;

class Node {
    public int val;
    public Node left, right;
    public Node(int v) { val = v; left = right = null; }
}

class BST {
    public Node root;

    public Node Insert(Node root, int val) {
        if (root == null) return new Node(val);
        if (val < root.val) root.left = Insert(root.left, val);
        else root.right = Insert(root.right, val);
        return root;
    }

    public Node MinValueNode(Node node) {
        Node current = node;
        while (current.left != null) current = current.left;
        return current;
    }

    public Node InorderSuccessor(Node root, Node n) {
        if (n.right != null) return MinValueNode(n.right);
        Node succ = null;
        while (root != null) {
            if (n.val <= root.val) {
                succ = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return succ;
    }
}

class Program {
    static void Main() {
        BST tree = new BST();
        int[] values = {20, 8, 22, 4, 12, 10, 14};
        foreach (int v in values) tree.root = tree.Insert(tree.root, v);
        Node node = new Node(10);
        Node succ = tree.InorderSuccessor(tree.root, node);
        Console.WriteLine(succ != null ? succ.val.ToString() : "null");
    }
}

A The code runs and prints 20

B The code runs and prints 14

C The code runs and prints 12

D The code runs and prints null

💡 Hint

Check the condition inside the while loop for updating successor.

The condition uses <= which causes the loop to move left even when n.val == root.val, skipping the correct path. The successor found is 20, which is correct for node 10 in this tree.

❓ Predict Output

advanced

Inorder successor of the maximum node

What will be the output of this C# code when finding the inorder successor of the node with value 22 in the BST?

DSA C#

using System;

class Node {
    public int val;
    public Node left, right;
    public Node(int v) { val = v; left = right = null; }
}

class BST {
    public Node root;

    public Node Insert(Node root, int val) {
        if (root == null) return new Node(val);
        if (val < root.val) root.left = Insert(root.left, val);
        else root.right = Insert(root.right, val);
        return root;
    }

    public Node MinValueNode(Node node) {
        Node current = node;
        while (current.left != null) current = current.left;
        return current;
    }

    public Node InorderSuccessor(Node root, Node n) {
        if (n.right != null) return MinValueNode(n.right);
        Node succ = null;
        while (root != null) {
            if (n.val < root.val) {
                succ = root;
                root = root.left;
            } else if (n.val > root.val) {
                root = root.right;
            } else break;
        }
        return succ;
    }
}

class Program {
    static void Main() {
        BST tree = new BST();
        int[] values = {20, 8, 22, 4, 12, 10, 14};
        foreach (int v in values) tree.root = tree.Insert(tree.root, v);
        Node node = new Node(22);
        Node succ = tree.InorderSuccessor(tree.root, node);
        Console.WriteLine(succ != null ? succ.val.ToString() : "null");
    }
}

A null

B 20

C 8

D 22

💡 Hint

The maximum node in BST has no inorder successor.

Node 22 is the maximum node in the BST and has no right child, so its inorder successor is null.

🧠 Conceptual

expert

Inorder successor with parent pointer

Given a BST where each node has a parent pointer, which of the following is the correct logic to find the inorder successor of a node n?

A If n has right child, successor is rightmost node in right subtree; else successor is leftmost node in left subtree.

B If n has left child, successor is rightmost node in left subtree; else move up using parent until node is right child of its parent, then return that parent.

C Successor is always the parent node regardless of children.

D If n has right child, successor is leftmost node in right subtree; else move up using parent until node is left child of its parent, then return that parent.

💡 Hint

Think about inorder traversal and how parent pointers help find successor without root.

Inorder successor is the smallest node greater than n. If n has right child, it's the leftmost node in right subtree. Otherwise, move up parents until you find a node which is left child of its parent; that parent is successor.

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