BST Inorder Predecessor in DSA C#

Mental Model

The inorder predecessor of a node in a BST is the node that comes just before it in sorted order. It is the largest node smaller than the given node.

Analogy: Imagine a line of people sorted by height. The inorder predecessor of a person is the tallest person who is shorter than them, standing just before them in line.

       5
      / \
     3   7
    / \   \
   2   4   8

Node: 5 ↑
Inorder predecessor: 4

Dry Run Walkthrough

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

Goal: Find the node that comes just before 5 in sorted order, which is the inorder predecessor.

Step 1: Start at node 5, check if it has a left child

5 -> [left->3] -> 7 -> null

Why: The inorder predecessor is the maximum node in the left subtree if left child exists

Step 2: Move to left child 3, then go to its right child 4

3 -> [right->4] -> null

Why: We want the largest node in left subtree, so keep going right

Step 3: Node 4 has no right child, stop here

4 -> null

Why: This is the maximum node in left subtree, so it is the inorder predecessor

Result:

4 -> null
Inorder predecessor of 5 is 4

Annotated Code

DSA C#

using System;

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

public class BST
{
    public Node root;

    // Find inorder predecessor of given node
    public Node InorderPredecessor(Node node)
    {
        if (node == null) return null;

        // If left child exists, predecessor is max in left subtree
        if (node.left != null)
        {
            Node curr = node.left;
            // Move right as far as possible
            while (curr.right != null)
            {
                curr = curr.right; // advance curr to right child
            }
            return curr; // found max in left subtree
        }

        // If no left child, predecessor is one of ancestors
        Node predecessor = null;
        Node currNode = root;
        while (currNode != null)
        {
            if (node.val > currNode.val)
            {
                predecessor = currNode; // potential predecessor
                currNode = currNode.right; // move right to find closer
            }
            else if (node.val < currNode.val)
            {
                currNode = currNode.left; // move left
            }
            else
            {
                break; // found node
            }
        }
        return predecessor;
    }

    // Insert node in BST
    public void Insert(int val)
    {
        root = InsertRec(root, val);
    }

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

    // Print inorder traversal
    public void PrintInorder(Node node)
    {
        if (node == null) return;
        PrintInorder(node.left);
        Console.Write(node.val + " ");
        PrintInorder(node.right);
    }
}

public class Program
{
    public static void Main()
    {
        BST tree = new BST();
        int[] values = {5, 3, 7, 2, 4, 8};
        foreach (int v in values) tree.Insert(v);

        Node target = tree.root; // node with value 5
        Node pred = tree.InorderPredecessor(target);

        Console.Write("Inorder traversal: ");
        tree.PrintInorder(tree.root);
        Console.WriteLine();

        if (pred != null)
            Console.WriteLine($"Inorder predecessor of {target.val} is {pred.val}");
        else
            Console.WriteLine($"No inorder predecessor for {target.val}");
    }
}

while (curr.right != null) { curr = curr.right; // advance curr to right child }

advance curr to rightmost node in left subtree to find max

while (currNode != null) { if (node.val > currNode.val) { predecessor = currNode; // potential predecessor currNode = currNode.right; // move right to find closer }

search ancestors to find closest smaller node when no left subtree

Output

Inorder traversal: 2 3 4 5 7 8 

Inorder predecessor of 5 is 4

Complexity Analysis

Time: O(h) because we traverse down the tree height h to find predecessor

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

vs Alternative: Compared to inorder traversal of entire tree O(n), this method is faster as it only traverses path from root to node and possibly left subtree

Edge Cases

Node has no left child and is the smallest node

No inorder predecessor exists, function returns null

DSA C#

if (node.left != null)

Node has left subtree with multiple nodes

Function correctly finds the rightmost node in left subtree as predecessor

DSA C#

while (curr.right != null)

Node is null

Function returns null safely

DSA C#

if (node == null) return null;

When to Use This Pattern

When asked to find the previous node in sorted order in a BST, use the inorder predecessor pattern to find the largest smaller node efficiently.

Common Mistakes

Mistake: Trying to find predecessor by doing full inorder traversal and then searching
Fix: Use BST properties to find predecessor by checking left subtree or ancestors without full traversal

Mistake: Not handling the case when node has no left child and predecessor is ancestor
Fix: Include ancestor search logic when left subtree is absent

Summary

Finds the node that comes just before a given node in BST sorted order.

Use when you need the previous smaller value relative to a node in BST.

If left subtree exists, predecessor is max there; otherwise, it is the closest ancestor smaller than the node.

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