BST Inorder Predecessor in DSA C++ - Deep Dive

Overview - BST Inorder Predecessor

What is it?

A Binary Search Tree (BST) is a tree where each node has at most two children, and the left child's value is less than the parent, while the right child's value is greater. The inorder predecessor of a node in a BST is the node that comes immediately before it when the tree is traversed in sorted order (inorder traversal). Finding the inorder predecessor helps in many operations like deletion or finding closest smaller values.

Why it matters

Without the concept of an inorder predecessor, it would be hard to efficiently find the closest smaller value to a given node in a BST. This makes operations like node deletion or range queries inefficient or complicated. Understanding inorder predecessor helps maintain the BST's sorted property and perform updates or queries quickly.

Where it fits

Before learning inorder predecessor, you should understand BST structure and inorder traversal. After mastering this, you can learn about inorder successor, BST deletion algorithms, and balanced BSTs like AVL or Red-Black trees.

Mental Model

Core Idea

The inorder predecessor of a node in a BST is the largest node smaller than that node, found by looking left once and then as far right as possible.

Think of it like...

Imagine a line of people sorted by height. The inorder predecessor of a person is the tallest person who is just shorter than them, found by looking to the left and then moving right to find the closest taller person who is still shorter.

          ┌───────────────┐
          │     Node X     │
          └───────┬───────┘
                  │
          ┌───────┴───────┐
          │   Left Child  │
          └───────┬───────┘
                  │
          ┌───────┴───────┐
          │ Rightmost Node│
          └───────────────┘

Inorder Predecessor = Rightmost node in left subtree of Node X

Build-Up - 7 Steps

1

Foundation

Understanding BST Structure

Concept: Learn what a Binary Search Tree is and how nodes are arranged.

A BST is a tree where each node has a value. For any node, all values in its left subtree are smaller, and all values in its right subtree are larger. This property helps keep data sorted and allows fast searching.

Result

You can quickly find if a value exists by comparing and moving left or right.

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

2

Foundation

Inorder Traversal Basics

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

Inorder traversal visits the left subtree, then the node itself, then the right subtree. For BST, this means visiting nodes in ascending order of their values.

Result

The output of inorder traversal is a sorted list of all node values.

Knowing inorder traversal order helps understand why the predecessor is the previous node in this sequence.

3

Intermediate

Defining Inorder Predecessor

Concept: Identify what the inorder predecessor means in the BST context.

The inorder predecessor of a node is the node that appears immediately before it in the inorder traversal sequence. It is the largest value smaller than the current node's value.

Result

For example, in the sequence 2, 5, 7, 10, the predecessor of 7 is 5.

Understanding predecessor as the previous node in sorted order clarifies its role in BST operations.

4

Intermediate

Finding Predecessor When Left Subtree Exists

🤔Before reading on: do you think the predecessor is always the left child? Commit to yes or no.

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

Start at the left child, then keep moving right until you can't go further. That node is the predecessor because it is the largest smaller value.

Result

For node 10 with left child 7, and 7 has right child 9, predecessor is 9.

Knowing to go left once and then right as far as possible finds the closest smaller value efficiently.

5

Intermediate

Finding Predecessor Without Left Subtree

🤔Before reading on: if no left child, is the predecessor always the parent? Commit to yes or no.

Concept: If no left child, move up the tree until you find a node that is a right child of its parent; that parent is the predecessor.

Climb up using parent links until you find a node that is right child of its parent. That parent is the predecessor because it is smaller but closest in order.

Result

For node 5 with no left child, if it is left child of 7, predecessor is 2 (found by climbing up).

Understanding climbing up the tree to find predecessor handles cases without left subtree.

6

Advanced

Implementing Predecessor in C++

🤔Before reading on: do you think the code needs parent pointers to find predecessor? Commit to yes or no.

Concept: Write code to find inorder predecessor using left subtree or parent climbing, assuming parent pointers exist.

```cpp struct Node { int val; Node* left; Node* right; Node* parent; }; Node* inorderPredecessor(Node* node) { if (!node) return nullptr; if (node->left) { Node* pred = node->left; while (pred->right) pred = pred->right; return pred; } Node* p = node->parent; while (p && node == p->left) { node = p; p = p->parent; } return p; } ```

Result

The function returns the correct predecessor node or nullptr if none exists.

Knowing the two cases and how to implement them in code is key to practical BST manipulation.

7

Expert

Predecessor Without Parent Pointers

🤔Before reading on: can you find predecessor without parent pointers? Commit to yes or no.

Concept: Find predecessor by searching from the root if parent pointers are not available.

Start at root and track the last node smaller than target. Move left or right comparing values until you find the target node. The last smaller node tracked is the predecessor.

Result

You can find predecessor without extra memory but with O(h) time, where h is tree height.

Understanding this approach helps when parent pointers are not stored, common in many BST implementations.

Under the Hood

The BST property ensures all left subtree nodes are smaller and right subtree nodes are larger. The inorder predecessor is found by exploiting this property: if left subtree exists, the predecessor is the maximum node there; otherwise, it is found by moving up ancestors until a node is a right child of its parent. This works because inorder traversal visits nodes in ascending order, so the predecessor is the last smaller node visited before the current node.

Why designed this way?

This method leverages the BST's sorted structure to find predecessor efficiently without scanning the entire tree. Alternatives like scanning all nodes would be slower. Parent pointers simplify upward traversal but are optional; searching from root is a tradeoff for memory vs time. This design balances speed and memory use.

Root
 │
 ├── Left Subtree
 │    └── Rightmost Node (Predecessor if left subtree exists)
 └── Node X
      ↑
      └── Parent chain upward (Predecessor if no left subtree)

Traversal:
If node->left exists -> go left, then right as far as possible
Else -> go up until node is right child, then parent is predecessor

Myth Busters - 3 Common Misconceptions

Quick: Is the inorder predecessor always the left child? Commit 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 not be the immediate left child.

Why it matters: Assuming the left child is always predecessor causes wrong results and bugs in BST operations like deletion.

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

Common Belief: If no left child, the parent is always the predecessor.

Reality: The predecessor is the nearest ancestor for which the node is in the right subtree, not necessarily the immediate parent.

Why it matters: Wrong assumptions lead to incorrect predecessor and break tree operations that rely on correct predecessor.

Quick: Can you find inorder predecessor without parent pointers easily? Commit yes or no.

Common Belief: You must have parent pointers to find the predecessor efficiently.

Reality: You can find predecessor by searching from the root and tracking candidates without parent pointers.

Why it matters: Believing parent pointers are mandatory limits understanding and implementation options.

Expert Zone

1

When climbing up to find predecessor, stopping at the first ancestor where current node is in right subtree is subtle but critical.

2

In threaded BSTs, predecessor pointers are stored explicitly, optimizing traversal but complicating insertion/deletion.

3

In balanced BSTs, predecessor finding is similar but tree rotations can temporarily affect correctness if not handled carefully.

When NOT to use

If the BST is not balanced, predecessor search can degrade to O(n) time. For very large datasets, balanced trees or augmented data structures like order-statistics trees are better. Also, if parent pointers are not stored and root is unknown, predecessor finding is impractical.

Production Patterns

In production, inorder predecessor is used in BST node deletion to replace a node with its predecessor for maintaining BST properties. It is also used in range queries to find closest smaller values and in database indexing where BST-like structures are common.

Connections

Inorder Successor

Opposite concept in BST traversal order

Understanding predecessor clarifies successor logic since both are neighbors in sorted order, enabling symmetric tree operations.

Doubly Linked List

Similar concept of previous and next nodes

Knowing predecessor in BST helps understand how doubly linked lists maintain order with previous pointers, linking tree and list data structures.

Version Control Systems (Git)

Finding previous commit is like finding predecessor

The idea of predecessor as the immediate prior element in a sequence applies in version control history navigation, showing cross-domain pattern of ordered predecessor.

Common Pitfalls

#1 Assuming left child is always predecessor

Wrong approach:

Node* pred = node->left; return pred;

Correct approach:

Node* pred = node->left;
while (pred && pred->right) pred = pred->right;
return pred;

Root cause:

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

#2 Returning parent as predecessor without checking subtree position

Wrong approach:

if (!node->left) return node->parent;

Correct approach:

Node* p = node->parent;
while (p && node == p->left) {
node = p;
p = p->parent;
}
return p;

Root cause:

Ignoring that predecessor is the ancestor where node is in right subtree, not just any parent.

#3 Trying to find predecessor without root or parent pointers by only local checks

Wrong approach:

if (!node->left) return nullptr; // no parent pointers, no root given

Correct approach:

Use a search from root to track last smaller node while searching for target node.

Root cause:

Not realizing predecessor can be found by global search from root when parent pointers are missing.

Key Takeaways

The inorder predecessor of a BST node is the largest node smaller than it, found by going left once and then right as far as possible.

If no left subtree exists, the predecessor is found by moving up ancestors until the node is a right child of its parent.

Parent pointers simplify predecessor finding, but it can also be done by searching from the root without them.

Correctly finding the inorder predecessor is essential for BST operations like deletion and range queries.

Misunderstanding predecessor logic leads to bugs; knowing the two main cases prevents common errors.

Practice

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

easy

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

B. The node with the largest value smaller 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 in BST

   Inorder traversal visits nodes in ascending order of their values.

2. Step 2: Define inorder predecessor

   The inorder predecessor of a node is the node visited just before it in inorder traversal, which means it has the largest value smaller than the current node.

3. Final Answer:

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

4. Quick Check:

   Inorder predecessor = largest smaller value [OK]

Hint: Predecessor is just before in sorted order [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++ function signatures correctly represents a function to find the inorder predecessor of a BST node given its pointer Node* root and Node* target?

easy

A. Node* findInorderPredecessor(Node* root, Node* target);

B. void findInorderPredecessor(Node* root, int target);

C. int findInorderPredecessor(Node* root, Node* target);

D. Node findInorderPredecessor(Node root, Node target);

Solution

1. Step 1: Analyze parameter types

   The function needs the root pointer and the target node pointer to find the predecessor.

2. Step 2: Analyze return type

   The predecessor is a node pointer, so return type should be Node*.

3. Final Answer:

   Node* findInorderPredecessor(Node* root, Node* target); -> Option A

4. Quick Check:

   Correct parameters and return type [OK]

Hint: Return pointer to predecessor node [OK]

Common Mistakes:

• Using int return type instead of Node*
• Passing target as int instead of Node*
• Passing nodes by value instead of pointer

3. Consider the following BST and code snippet to find the inorder predecessor of node with value 15:

struct Node {
  int val;
  Node* left;
  Node* right;
};

Node* findMax(Node* root) {
  while (root->right) root = root->right;
  return root;
}

Node* inorderPredecessor(Node* root, Node* target) {
  if (target->left) return findMax(target->left);
  Node* predecessor = nullptr;
  while (root) {
    if (target->val > root->val) {
      predecessor = root;
      root = root->right;
    } else if (target->val < root->val) {
      root = root->left;
    } else break;
  }
  return predecessor;
}

// BST structure:
//        20
//       /  \
//     10    30
//       \     \
//       15    40

Node* root = ...; // root of above BST
Node* target = root->left->right; // node with value 15
Node* pred = inorderPredecessor(root, target);
std::cout << pred->val << std::endl;

What is the output?

medium

A. 10

B. 15

C. 20

D. 30

Solution

1. Step 1: Check if target has left subtree

   Node 15 has no left child, so we skip findMax on left subtree.

2. Step 2: Traverse from root to find predecessor

   Start at root (20). Since 15 < 20, go left to 10. Since 15 > 10, set predecessor = 10 and go right to 15. Found target, stop.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Largest smaller value than 15 is 10 [OK]

Hint: If no left child, track last smaller ancestor [OK]

Common Mistakes:

• Returning target node itself
• Returning root node 20 incorrectly
• Confusing predecessor with successor

4. The following code attempts to find the inorder predecessor of a node in a BST but has a bug. Identify the bug.

Node* inorderPredecessor(Node* root, Node* target) {
  if (target->left) {
    Node* temp = target->left;
    while (temp->left) temp = temp->left;
    return temp;
  }
  Node* predecessor = nullptr;
  while (root) {
    if (target->val > root->val) {
      predecessor = root;
      root = root->right;
    } else if (target->val < root->val) {
      root = root->left;
    } else break;
  }
  return predecessor;
}

medium

A. The predecessor variable is not initialized

B. The function does not handle the case when target has no left subtree

C. The function returns nullptr always

D. The loop to find max in left subtree incorrectly goes left instead of right

Solution

1. Step 1: Check left subtree max search

   To find inorder predecessor in left subtree, we must find the maximum node, which is the rightmost node, but code goes left repeatedly.

2. Step 2: Confirm other parts are correct

   The rest of the code correctly handles cases without left subtree and initializes predecessor.

3. Final Answer:

   The loop to find max in left subtree incorrectly goes left instead of right -> Option D

4. Quick Check:

   Max in left subtree requires right traversal [OK]

Hint: Max in left subtree means go right, not left [OK]

Common Mistakes:

• Going left instead of right to find max
• Not checking if target->left is null
• Confusing predecessor with successor

5. Given a BST with nodes inserted in this order: 25, 15, 50, 10, 22, 35, 70, 4, 12, 18, 24, 31, 44, 66, 90. Write a function to find the inorder predecessor of a node with value 31. What will be the predecessor's value? Hint: Use the BST property and consider both cases when the node has a left subtree or not.

hard

A. 25

B. 35

C. 24

D. 22

Solution

1. Step 1: Locate node 31

   Node 31 is the left child of 35 and has no left subtree.

2. Step 2: Traverse from root to find predecessor

   Start at root 25 (31 > 25, predecessor=25, go right to 50). 31 < 50, go left to 35. 31 < 35, go left to 31. Found target, predecessor=25.

3. Step 3: Verify with inorder traversal

   Inorder traversal sequence around 31 is ... 24, 25, 31, 35 ... The predecessor of 31 is the largest smaller value, which is 24 (left subtree of 25).

4. Final Answer:

   24 -> Option C

5. Quick Check:

   Inorder predecessor of 31 is 24 [OK]

Hint: If no left child, predecessor is last smaller ancestor or max in left subtree [OK]

Common Mistakes:

• Choosing 25 instead of 24
• Choosing successor 35 instead of predecessor
• Ignoring left subtree check