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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Inorder Predecessor Search in BST

What is the output of the following C# code that finds the inorder predecessor of a node with value 15 in the given 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 InorderPredecessor(Node root, int key) {
        Node predecessor = null;
        Node current = root;
        while (current != null) {
            if (key <= current.val) {
                current = current.left;
            } else {
                predecessor = current;
                current = current.right;
            }
        }
        return predecessor;
    }
}

class Program {
    static void Main() {
        BST tree = new BST();
        tree.root = new Node(20);
        tree.root.left = new Node(10);
        tree.root.right = new Node(30);
        tree.root.left.left = new Node(5);
        tree.root.left.right = new Node(15);
        tree.root.right.right = new Node(40);

        Node pred = tree.InorderPredecessor(tree.root, 15);
        Console.WriteLine(pred != null ? pred.val.ToString() : "null");
    }
}

A 15

B 10

C 5

D null

💡 Hint

Remember, inorder predecessor is the largest value smaller than the given key.

The inorder predecessor of 15 is the largest node smaller than 15. In the BST, 10 is smaller than 15 and is the closest smaller value. So the output is 10.

🧠 Conceptual

intermediate

Understanding Inorder Predecessor in BST

In a Binary Search Tree (BST), which of the following best describes the inorder predecessor of a node with value X?

A The node with the largest value smaller than X

B The left child of node X

C The node with the smallest value greater than X

D The right child of node X

💡 Hint

Think about the inorder traversal order and what comes just before X.

Inorder traversal visits nodes in ascending order. The inorder predecessor of X is the node visited just before X, which is the largest value smaller than X.

❓ Predict Output

advanced

Output of Inorder Predecessor with Node Having Left Subtree

What will be the output of the following code that finds the inorder predecessor of node with value 20 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 FindNode(Node root, int key) {
        if (root == null) return null;
        if (root.val == key) return root;
        if (key < root.val) return FindNode(root.left, key);
        else return FindNode(root.right, key);
    }

    public Node InorderPredecessor(Node root, int key) {
        Node target = FindNode(root, key);
        if (target == null) return null;

        if (target.left != null) {
            Node temp = target.left;
            while (temp.right != null) temp = temp.right;
            return temp;
        }

        Node predecessor = null;
        Node current = root;
        while (current != null) {
            if (key > current.val) {
                predecessor = current;
                current = current.right;
            } else if (key < current.val) {
                current = current.left;
            } else {
                break;
            }
        }
        return predecessor;
    }
}

class Program {
    static void Main() {
        BST tree = new BST();
        tree.root = new Node(20);
        tree.root.left = new Node(10);
        tree.root.right = new Node(30);
        tree.root.left.left = new Node(5);
        tree.root.left.right = new Node(15);
        tree.root.left.right.left = new Node(12);

        Node pred = tree.InorderPredecessor(tree.root, 20);
        Console.WriteLine(pred != null ? pred.val.ToString() : "null");
    }
}

A null

B 12

C 10

D 15

💡 Hint

If the node has a left subtree, the predecessor is the rightmost node in that subtree.

Node 20 has a left child 10. The rightmost node in 10's subtree is 15, so 15 is the inorder predecessor.

🔧 Debug

advanced

Identify the Error in Inorder Predecessor Code

What error will the following code produce when trying to find the inorder predecessor of 10 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 InorderPredecessor(Node root, int key) {
        Node predecessor = null;
        Node current = root;
        while (current != null) {
            if (key < current.val) {
                current = current.left;
            } else if (key > current.val) {
                predecessor = current;
                current = current.right;
            } else {
                if (current.left != null) {
                    Node temp = current.left;
                    while (temp.right != null) temp = temp.right;
                    return temp;
                }
                break;
            }
        }
        return predecessor;
    }
}

class Program {
    static void Main() {
        BST tree = new BST();
        tree.root = new Node(20);
        tree.root.left = new Node(10);
        tree.root.right = new Node(30);
        tree.root.right.left = new Node(25);
        tree.root.right.right = new Node(40);

        Node pred = tree.InorderPredecessor(tree.root, 10);
        if (pred != null) {
            Console.WriteLine(pred.val);
        } else {
            Console.WriteLine("null");
        }
    }
}

A Output: 20

B StackOverflowException

C NullReferenceException

D Output: 25

💡 Hint

Check what happens if predecessor is null before accessing its val.

If the predecessor is null, accessing pred.val causes NullReferenceException. Here, predecessor is null because 10 has no left subtree and no smaller ancestor.

🚀 Application

expert

Number of Nodes in Result of Inorder Predecessor Search

Given a BST with nodes [50, 30, 70, 20, 40, 60, 80], how many nodes will be visited in total when searching for the inorder predecessor of 65 using the standard BST inorder predecessor algorithm?

A 3

B 4

C 5

D 6

💡 Hint

Trace the path from root to the node or where the node would be inserted.

Searching for 65, path is 50 -> 70 -> 60 (since 65 < 70, go left). Nodes visited: 50, 70, 60. Total 3 nodes.

Practice

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

easy

A. The node with the largest value smaller than the given node

B. The node with the smallest value larger than the given node

C. The left child of the given node

D. The right child of the given node

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits nodes in ascending order for BST.

2. Step 2: Define predecessor in inorder traversal

   The predecessor is the node visited just before the current node, so it must have the largest value smaller than the current node.

3. Final Answer:

   The node with the largest value smaller than the given node -> Option A

4. Quick Check:

   Inorder predecessor = largest smaller value [OK]

Hint: Predecessor is largest smaller value in BST [OK]

Common Mistakes:

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

2. Which of the following C# code snippets correctly finds the inorder predecessor of a node with a left subtree in a BST?

easy

A. Node predecessor = node.Left; while (predecessor.Left != null) predecessor = predecessor.Left;

B. Node predecessor = node.Right; while (predecessor.Left != null) predecessor = predecessor.Left;

C. Node predecessor = node.Right; while (predecessor.Right != null) predecessor = predecessor.Right;

D. Node predecessor = node.Left; while (predecessor.Right != null) predecessor = predecessor.Right;

Solution

1. Step 1: Check where predecessor lies if left subtree exists

   Predecessor is the rightmost node in the left subtree.

2. Step 2: Analyze code snippets

   Node predecessor = node.Left; while (predecessor.Right != null) predecessor = predecessor.Right; starts at left child and moves right until no more right child, correctly finding predecessor.

3. Final Answer:

   Node predecessor = node.Left; while (predecessor.Right != null) predecessor = predecessor.Right; -> Option D

4. Quick Check:

   Left subtree's rightmost node = predecessor [OK]

Hint: Go left once, then right as far as possible [OK]

Common Mistakes:

• Going left repeatedly instead of right in left subtree
• Starting from right child instead of left
• Ignoring the while loop to find rightmost node

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

       20
      /  \
    10    30
      \
      15

medium

A. 30

B. 10

C. 20

D. 15

Solution

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

   Node 15 has no left child, so predecessor is ancestor smaller than 15.

2. Step 2: Find nearest ancestor smaller than 15

   Ancestor 10 is smaller than 15 and is the closest on the path.

3. Final Answer:

   10 -> Option B

4. Quick Check:

   Predecessor of 15 is 10 [OK]

Hint: If no left child, go up to smaller ancestor [OK]

Common Mistakes:

• Choosing 20 which is larger than 15
• Choosing 15 itself
• Choosing 30 which is right subtree

4. Consider the following C# method to find the inorder predecessor of a node in a BST. What is the bug?

Node FindPredecessor(Node root, Node node) {
  if (node.Left != null) {
    Node temp = node.Left;
    while (temp.Left != null) {
      temp = temp.Left;
    }
    return temp;
  }
  Node predecessor = null;
  Node current = root;
  while (current != null) {
    if (node.Value > current.Value) {
      predecessor = current;
      current = current.Right;
    } else {
      current = current.Left;
    }
  }
  return predecessor;
}

medium

A. The while loop should check temp.Right, not temp.Left

B. The method does not handle null root

C. The method returns node itself as predecessor

D. The method incorrectly updates predecessor in the else block

Solution

1. Step 1: Analyze left subtree traversal

   Predecessor in left subtree is rightmost node, so loop should move right, not left.

2. Step 2: Identify incorrect loop condition

   Current code loops while temp.Left != null, should be temp.Right != null to find rightmost node.

3. Final Answer:

   The while loop should check temp.Right, not temp.Left -> Option A

4. Quick Check:

   Rightmost node in left subtree = predecessor [OK]

Hint: Go right in left subtree to find predecessor [OK]

Common Mistakes:

• Checking left child repeatedly instead of right
• Ignoring null root case (not critical here)
• Confusing predecessor update logic

5. You want to find the inorder predecessor of a node with value 25 in the BST below:

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

Which node is the inorder predecessor of 25?

hard

A. 30

B. 10

C. 20

D. 25 has no predecessor

Solution

1. Step 1: Check if node 25 has left subtree

   Node 25 has no left child, so predecessor is ancestor smaller than 25.

2. Step 2: Find nearest ancestor smaller than 25

   Ancestor 20 is smaller than 25 and closest on path from root to 25.

3. Final Answer:

   20 -> Option C

4. Quick Check:

   Predecessor of 25 is 20 [OK]

Hint: If no left child, predecessor is nearest smaller ancestor [OK]

Common Mistakes:

• Choosing 30 which is larger than 25
• Choosing 10 which is smaller but not nearest ancestor
• Thinking 25 has no predecessor