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 traversal of a BST visits nodes in ascending order. The inorder predecessor of a node is the node that comes immediately before it in this sorted order. Finding the inorder predecessor helps in many tree operations like deletion or finding closest smaller values.

Why it matters

Without knowing the inorder predecessor, operations like deleting a node with two children become complicated and inefficient. It helps maintain the BST properties after changes. In real life, this is like knowing the previous item in a sorted list without having to sort again. Without this concept, many tree algorithms would be slower or more complex, affecting software performance and correctness.

Where it fits

Before learning this, you should understand basic BST structure and inorder traversal. After mastering inorder predecessor, you can learn about inorder successor, tree 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 it, found by looking left once and then as far right as possible.

Think of it like...

Imagine a line of people sorted by height. To find the person just shorter than a given person, you look to the left group and find the tallest person there. That tallest shorter person is the predecessor.

        [Node]
          /   \
   [Left Subtree]  [Right Subtree]

Inorder predecessor:
- Go to left child
- Then keep going right until no more right child
- That node is the predecessor

Build-Up - 7 Steps

1

Foundation

Understanding BST Structure

Concept: Learn what a BST is and how nodes are arranged.

A BST is a tree where each node has a value. Left child nodes have smaller values; right child nodes have larger values. This property helps us quickly find values by comparing and moving left or right.

Result

You can visualize a BST as a sorted structure where smaller values go left and larger values go right.

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

2

Foundation

Inorder Traversal Basics

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

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

Result

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

Knowing inorder traversal order helps us understand what 'predecessor' means in the BST context.

3

Intermediate

Defining Inorder Predecessor

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

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

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

Result

You can find the predecessor by either going left then right as far as possible, or moving up to ancestors.

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

4

Intermediate

Finding Predecessor with Left Subtree

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

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

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

Result

You find the largest smaller value in the left subtree, which is the predecessor.

Knowing to go right inside the left subtree finds the closest smaller value, not just the immediate left child.

5

Intermediate

Finding Predecessor Without Left Subtree

🤔Before reading on: if no left subtree, do you think the predecessor is below or above the node? Commit to your answer.

Concept: If no left subtree, predecessor is an ancestor node where current node is in its 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.

Result

You find the closest smaller ancestor node, which is the predecessor.

Understanding ancestor traversal is key when left subtree is missing, preventing dead ends.

6

Advanced

Implementing Predecessor in C

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

Concept: Efficient predecessor finding often requires parent pointers or a stack to track ancestors.

Use a function that: - If left child exists, go left then rightmost. - Else, move up parents until node is right child. Example code snippet: struct Node { int val; struct Node *left, *right, *parent; }; struct Node* inorderPredecessor(struct Node* node) { if (node->left) { struct Node* pred = node->left; while (pred->right) pred = pred->right; return pred; } struct 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 NULL if none exists.

Knowing parent pointers simplifies ancestor traversal, making code cleaner and faster.

7

Expert

Predecessor in BST Without Parent Pointers

🤔Before reading on: can you find predecessor without parent pointers in O(h) time? Commit to yes or no.

Concept: Without parent pointers, you can find predecessor by starting from root and searching down, tracking candidate predecessor.

Start at root: - If node value > target, go left. - If node value < target, update candidate predecessor and go right. - Repeat until target found. Candidate holds predecessor. Example code: struct Node* findPredecessor(struct Node* root, int key) { struct Node* pred = NULL; while (root) { if (key <= root->val) root = root->left; else { pred = root; root = root->right; } } return pred; }

Result

You get the predecessor without needing parent pointers, in O(height) time.

Tracking candidate predecessor during search leverages BST properties to avoid parent pointers.

Under the Hood

The BST property orders nodes so that inorder traversal visits nodes in ascending order. The predecessor is the node visited immediately before the current node. Internally, if the node has a left subtree, the predecessor is the rightmost node there because it is the largest smaller value. If no left subtree, the predecessor is an ancestor node where the current node lies in the right subtree, found by moving up parent links until a right turn is found.

Why designed this way?

This design leverages the BST's sorted structure to find predecessor efficiently without full traversal. Alternatives like full inorder traversal are slower. Parent pointers or tracking candidate predecessors during search optimize time complexity. This approach balances speed and memory use, fitting common BST operations like deletion.

Root
 │
 ├── Left Subtree
 │     └── Rightmost Node ← Predecessor if node has left child
 │
 └── Right Subtree

If no left child:
Node
 │
 ↑ (move up)
Ancestor where Node is in right subtree ← Predecessor

Myth Busters - 3 Common Misconceptions

Quick: Is the inorder predecessor always the left child of a node? 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 be deeper than the immediate left child.

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

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

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

Reality: The predecessor is the nearest ancestor where the node is in the right subtree, which may be higher than the parent or none at all.

Why it matters: Wrong assumptions lead to incorrect predecessor identification and break tree algorithms.

Quick: Can you find the predecessor in O(1) time without extra pointers? Commit yes or no.

Common Belief: You can find the predecessor instantly without parent pointers or extra memory.

Reality: Without parent pointers or extra memory, you must start from root and search, which takes O(height) time.

Why it matters: Expecting O(1) leads to inefficient or incorrect implementations.

Expert Zone

1

When parent pointers are missing, tracking candidate predecessor during search is a subtle but powerful technique.

2

In threaded BSTs, predecessor pointers are stored explicitly to speed up traversal, a design choice balancing memory and speed.

3

In deletion, choosing predecessor vs successor affects tree balance and performance subtly, important in balanced BSTs.

When NOT to use

If the BST is balanced and augmented with extra data, specialized methods like order statistics trees or balanced tree rotations are better. For very large trees, iterative or threaded BSTs may be preferred over recursive predecessor search.

Production Patterns

In production, inorder predecessor is used in node deletion to replace a node with two children, maintaining BST properties. It is also used in range queries and nearest smaller value searches in databases and file systems.

Connections

Inorder Successor

Opposite concept in BST traversal order

Understanding predecessor clarifies successor logic, as both rely on BST structure and traversal order.

Doubly Linked List

Similar concept of previous and next nodes

Knowing predecessor in BST helps understand previous pointers in doubly linked lists, both represent immediate neighbors in order.

Version Control Systems (Git)

Finding previous commit in history is like finding predecessor in a tree

Understanding predecessor in BST helps grasp how Git finds previous commits, showing cross-domain pattern of 'previous element' in ordered structures.

Common Pitfalls

#1 Assuming the left child is always the predecessor.

Wrong approach:

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

Correct approach:

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

Root cause:

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

#2 Trying to find predecessor without parent pointers by moving up from node.

Wrong approach:

struct Node* p = node->parent; // but parent pointer missing, leads to error

Correct approach:

Use root to search and track candidate predecessor:
struct Node* pred = NULL;
while (root) {
if (key <= root->val) root = root->left;
else {
pred = root;
root = root->right;
}
}
return pred;

Root cause:

Assuming parent pointers exist when they do not, causing invalid memory access or logic errors.

#3 Not handling case when predecessor does not exist (smallest node).

Wrong approach:

Always returning a node without checking if predecessor is NULL.

Correct approach:

Check if predecessor is NULL before using it to avoid null pointer errors.

Root cause:

Ignoring edge cases where node is the smallest in BST and has no predecessor.

Key Takeaways

The inorder predecessor is the node visited immediately before a given node in BST's sorted order.

If a node has a left subtree, its 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 predecessors, but without them, you can track candidate predecessors during search from the root.

Misunderstanding predecessor location leads to bugs in tree operations like deletion and traversal.

Knowing predecessor logic is essential for efficient BST manipulation and understanding related data structures.

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 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 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 given node node in a BST when the node has a left subtree?

easy

A. Node* pred = node->left; while (pred->right != NULL) pred = pred->right;

B. Node* pred = node->right; while (pred->left != NULL) pred = pred->left;

C. Node* pred = node->left; while (pred->left != NULL) pred = pred->left;

D. Node* pred = node->right; while (pred->right != NULL) pred = pred->right;

Solution

1. Step 1: Identify inorder predecessor in left subtree

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

2. Step 2: Trace code logic

   Starting from node->left, moving right until right child is NULL finds the rightmost node.

3. Final Answer:

   Node* pred = node->left; while (pred->right != NULL) pred = pred->right; -> Option A

4. Quick Check:

   Left subtree's rightmost node = predecessor [OK]

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

Common Mistakes:

• Going right subtree instead of left
• Moving left repeatedly instead of right
• Starting from node->right instead of node->left

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

        20
       /  \
     10    30
       \     \
       15    40

medium

A. 30

B. 15

C. 20

D. 10

Solution

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

   Node 15 has no left child, so predecessor is an 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 to root.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Predecessor of 15 is 10 [OK]

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

Common Mistakes:

• Choosing node itself as predecessor
• Choosing larger ancestor like 20
• Confusing predecessor with successor

4. Consider this buggy C function to find the inorder predecessor of a node in a BST:

Node* inorderPredecessor(Node* root, Node* node) {
    if (node->left != NULL) {
        Node* pred = node->left;
        while (pred->left != NULL) {
            pred = pred->left;
        }
        return pred;
    }
    Node* pred = NULL;
    Node* ancestor = root;
    while (ancestor != node) {
        if (node->data > ancestor->data) {
            pred = ancestor;
            ancestor = ancestor->right;
        } else {
            ancestor = ancestor->left;
        }
    }
    return pred;
}

What is the main error in this code?

medium

A. The ancestor traversal is incorrect and may cause infinite loop

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

C. The while loop should move right in left subtree, not left

D. The function returns NULL even if predecessor exists

Solution

1. Step 1: Analyze left subtree traversal

   In left subtree, predecessor is rightmost node, so loop should move right, not left.

2. Step 2: Check code loop

   Code incorrectly moves left repeatedly, so it finds leftmost node instead of rightmost.

3. Final Answer:

   The while loop should move right in left subtree, not left -> Option C

4. Quick Check:

   Left subtree traversal must go right for predecessor [OK]

Hint: In left subtree, go right to find predecessor [OK]

Common Mistakes:

• Moving left instead of right in left subtree
• Ignoring ancestor traversal logic
• Assuming predecessor is always left child

5. You have a BST where each node has a pointer to its parent. Write the logic to find the inorder predecessor of a node node that has no left child. Which approach correctly finds the predecessor?

hard

A. Return the right child of the node's parent

B. Move up using parent pointers until you find a node which is right child of its parent; then return that parent

C. Move up using parent pointers until you find a node which is left child of its parent; then return that parent

D. Return the left child of the node's parent

Solution

1. Step 1: Understand no left child case

   If node has no left child, predecessor is an ancestor where node is in right subtree.

2. Step 2: Use parent pointers to find such ancestor

   Move up until current node is right child of its parent; that parent is predecessor.

3. Final Answer:

   Move up using parent pointers until you find a node which is right child of its parent; then return that parent -> Option B

4. Quick Check:

   Go up to right-child parent for predecessor [OK]

Hint: Go up until node is right child, then parent is predecessor [OK]

Common Mistakes:

• Stopping at left child parent
• Returning sibling nodes incorrectly
• Assuming predecessor is always child node