BST Inorder Predecessor in DSA C# - Deep Dive

Overview - BST Inorder Predecessor

What is it?

A Binary Search Tree (BST) is a special tree where each node has a value, and all values in the left subtree are smaller, while all values in the right subtree are larger. The inorder predecessor of a node in a BST is the node that comes immediately before it when we list all nodes in ascending order. It helps us find the closest smaller value to a given node. This concept is useful when deleting nodes or navigating the tree.

Why it matters

Without knowing the inorder predecessor, operations like deleting a node with two children become complicated because we need a way to replace the node with a nearby value that keeps the BST rules intact. This concept helps maintain the tree's order and efficiency. Without it, searching and updating the tree would be slower and error-prone.

Where it fits

Before learning this, you should understand what a Binary Search Tree is and how inorder traversal works. After mastering the inorder predecessor, you can learn about inorder successor, node deletion in BST, and balanced trees like AVL or Red-Black trees.

Mental Model

Core Idea

The inorder predecessor of a node in a BST is the closest smaller value node that appears just before it in sorted order.

Think of it like...

Imagine a line of people sorted by height. The inorder predecessor of a person is the person just shorter than them standing immediately to their left.

BST Inorder Predecessor Visualization:

       20
      /  \
    10    30
      \     \
      15    40

Inorder traversal: 10 -> 15 -> 20 -> 30 -> 40

Inorder predecessor of 20 is 15 (the closest smaller value before 20).

Build-Up - 7 Steps

1

Foundation

Understanding Binary Search Tree Basics

Concept: Learn what a BST is and how its structure organizes data.

A Binary Search Tree is a tree where each node has up to two children. The left child contains values smaller than the node, and the right child contains values larger. This structure allows quick searching, insertion, and deletion by comparing values and moving left or right accordingly.

Result

You can quickly find if a value exists by moving left or right at each node based on comparisons.

Understanding the BST structure is essential because the inorder predecessor depends on this sorted arrangement.

2

Foundation

Inorder Traversal of BST

Concept: Learn how inorder traversal visits nodes in ascending order.

Inorder traversal means visiting the left subtree, then the current node, then the right subtree recursively. For BST, this visits nodes from smallest to largest value.

Result

The nodes are visited in sorted order, e.g., for the tree with nodes 10, 15, 20, 30, 40, the order is 10 -> 15 -> 20 -> 30 -> 40.

Knowing inorder traversal order helps us understand what 'predecessor' means in terms of node sequence.

3

Intermediate

Defining Inorder Predecessor Concept

🤔Before reading on: do you think the inorder predecessor is always the left child of a node? Commit to your answer.

Concept: The inorder predecessor is the node visited just before the current node in inorder traversal, not necessarily the left child.

If a node has a left subtree, the predecessor is the rightmost node in that left subtree. If no left subtree exists, the predecessor is one of the ancestors where the node lies in the right subtree.

Result

You can find the predecessor by either going left once and then all the way right, or by moving up to an ancestor.

Understanding that the predecessor depends on subtree structure or ancestors prevents wrong assumptions about its location.

4

Intermediate

Finding Predecessor When Left Subtree Exists

🤔Before reading on: if a node has a left child, do you think the predecessor is the left child itself or deeper? Commit to your answer.

Concept: When a left subtree exists, the predecessor is the rightmost node in that subtree.

Start at the left child, then keep moving right until no more right child exists. That node is the inorder predecessor.

Result

For node 20 in the example, left child is 10, rightmost node in left subtree is 15, so predecessor is 15.

Knowing to go right inside the left subtree ensures you find the closest smaller value, not just any smaller value.

5

Intermediate

Finding Predecessor When No Left Subtree

🤔Before reading on: if a node has no left child, do you think the predecessor is below or above it in the tree? Commit to your answer.

Concept: If no left subtree exists, the predecessor is an ancestor node where the current node is in the right subtree.

Move up the tree using parent links until you find a node that is a right child of its parent. That parent is the predecessor. If none found, no predecessor exists (node is smallest).

Result

For node 15, no left subtree, predecessor is 10 (ancestor). For node 10, no predecessor exists.

Recognizing the role of ancestors in predecessor finding completes the understanding of all cases.

6

Advanced

Implementing Inorder Predecessor in C#

🤔Before reading on: do you think the code should handle both cases (left subtree and no left subtree) separately? Commit to your answer.

Concept: Combine both cases in code to find the inorder predecessor efficiently.

public class TreeNode { public int val; public TreeNode left, right, parent; public TreeNode(int val) { this.val = val; } } public TreeNode InorderPredecessor(TreeNode node) { if (node == null) return null; // Case 1: Left subtree exists if (node.left != null) { TreeNode pred = node.left; while (pred.right != null) { pred = pred.right; } return pred; } // Case 2: No left subtree, go up ancestors TreeNode curr = node; TreeNode parent = curr.parent; while (parent != null && parent.left == curr) { curr = parent; parent = parent.parent; } return parent; }

Result

The function returns the inorder predecessor node or null if none exists.

Combining both cases in one function ensures correctness and efficiency in real-world BST operations.

7

Expert

Handling Edge Cases and Performance

🤔Before reading on: do you think the inorder predecessor search always takes O(log n) time in BST? Commit to your answer.

Concept: Understand edge cases like no predecessor and performance implications in unbalanced trees.

If the BST is balanced, finding predecessor takes O(log n) time. In worst case (skewed tree), it can be O(n). Also, if the node is the smallest, no predecessor exists (returns null). Handling parent pointers is crucial; if missing, alternative methods are needed.

Result

You know when the method is efficient and when it might slow down, and how to handle missing parent links.

Knowing performance and edge cases prepares you for real-world scenarios where trees are not perfect and data structures vary.

Under the Hood

The inorder predecessor search uses the BST property that left subtree nodes are smaller and right subtree nodes are larger. When a left subtree exists, the predecessor is the maximum node there (rightmost). Without a left subtree, the search climbs ancestors to find a node where the current node lies in the right subtree, ensuring the predecessor is the closest smaller ancestor. Parent pointers or stack-based traversal help navigate upwards.

Why designed this way?

This method leverages BST ordering to find the closest smaller value efficiently without scanning the entire tree. Alternatives like full traversal are slower. Using parent pointers or subtree navigation balances speed and simplicity. Historically, this approach evolved to support efficient deletion and traversal operations.

Inorder Predecessor Search Flow:

  [Start at node]
       |
       v
  [Has left subtree?] --Yes--> [Go left once]
       |                             |
       No                            v
       |                      [Go right until no right child]
       v                             |
  [Go up ancestors] <--- [Find ancestor where node is right child]
       |
       v
  [Return found node or null]

Myth Busters - 3 Common Misconceptions

Quick: Is the inorder predecessor always the left child of a node? Commit to yes or no.

Common Belief: The inorder predecessor is always the left child of the node.

Reality: The predecessor is the rightmost node in the left subtree, which may be deeper than the immediate left child.

Why it matters: Assuming the left child is the predecessor can cause incorrect results and bugs in tree operations like deletion.

Quick: If a node has no left child, is there always no predecessor? Commit to yes or no.

Common Belief: If a node has no left child, it has no inorder predecessor.

Reality: The predecessor can be an ancestor node where the current node is in the right subtree.

Why it matters: Ignoring ancestors leads to missing valid predecessors and breaks tree navigation logic.

Quick: Does finding the inorder predecessor always take O(log n) time? Commit to yes or no.

Common Belief: Finding the inorder predecessor is always fast, O(log n), in BSTs.

Reality: In unbalanced BSTs, the search can degrade to O(n) time in the worst case.

Why it matters: Assuming always fast can cause performance surprises in skewed trees.

Expert Zone

1

In BSTs without parent pointers, finding the predecessor requires a stack or recursive traversal from the root, increasing complexity.

2

When deleting a node, replacing it with its inorder predecessor maintains BST properties and avoids restructuring the entire tree.

3

In threaded BSTs, predecessor links are stored explicitly, allowing O(1) access without traversal.

When NOT to use

If the BST does not maintain parent pointers and memory is limited, using iterative traversal with a stack or Morris traversal is better. For balanced trees like AVL or Red-Black trees, specialized deletion algorithms handle predecessor finding internally. In non-BST trees, this concept does not apply.

Production Patterns

In production, inorder predecessor is used in node deletion to replace nodes with two children. It is also used in range queries and nearest smaller value searches. Parent pointers are often maintained for efficient upward navigation. Threaded BSTs use predecessor pointers to speed up traversals.

Connections

Inorder Successor

Opposite concept in BST traversal order

Understanding predecessor clarifies successor logic since both find closest neighbors in sorted order.

Doubly Linked List

Similar concept of predecessor and successor nodes

Knowing BST predecessor helps understand how doubly linked lists maintain backward and forward links.

Version Control Systems (Git)

Finding previous commit is like finding predecessor

The idea of predecessor as the immediate previous item in a sequence applies beyond trees, such as navigating commit history.

Common Pitfalls

#1 Assuming the inorder predecessor is always the left child node.

Wrong approach:

if (node.left != null) return node.left; else return null;

Correct approach:

if (node.left != null) { var pred = node.left; while (pred.right != null) pred = pred.right; return pred; } else { /* find ancestor */ }

Root cause:

Misunderstanding that predecessor is the maximum node in left subtree, not just the immediate left child.

#2 Not handling the case when the node has no left subtree and failing to check ancestors.

Wrong approach:

if (node.left == null) return null;

Correct approach:

if (node.left == null) { var curr = node; var parent = curr.parent; while (parent != null && parent.left == curr) { curr = parent; parent = parent.parent; } return parent; }

Root cause:

Ignoring ancestor traversal leads to missing valid predecessors.

#3 Assuming inorder predecessor search is always O(log n) without considering tree shape.

Wrong approach:

Assuming balanced tree always, ignoring skewed cases.

Correct approach:

Recognize worst-case O(n) time in skewed BSTs and optimize or rebalance tree accordingly.

Root cause:

Overgeneralizing performance without considering tree balance.

Key Takeaways

The inorder predecessor is the closest smaller node visited just before the current node in BST inorder traversal.

If a node has a left subtree, the predecessor is the rightmost node in that subtree; otherwise, it is an ancestor where the node lies in the right subtree.

Parent pointers simplify finding the predecessor by allowing upward traversal; without them, alternative methods are needed.

Understanding predecessor is essential for BST operations like deletion and maintaining sorted order.

Performance depends on tree balance; skewed trees can degrade predecessor search to linear time.

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