BST Inorder Predecessor in DSA Java - Deep Dive

Overview - BST Inorder Predecessor

What is it?

A Binary Search Tree (BST) is a special tree where each node has at most two children. The inorder predecessor of a node in a BST is the node that comes just before it when we list all nodes in ascending order. It helps us find the previous smaller value compared to a given node. This concept is useful in many tree operations like deletion or traversal.

Why it matters

Without knowing the inorder predecessor, it would be hard to efficiently find the previous smaller element in a BST. This would slow down operations like deleting a node or finding closest smaller values. In real life, this is like needing to find the previous page in a book quickly without flipping all pages. The inorder predecessor makes such lookups fast and organized.

Where it fits

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

Mental Model

Core Idea

The inorder predecessor of a node in a BST is the node with the largest value smaller than the given node, found by looking left once and then right as far 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 (shorter side) and then find the tallest person there. That tallest shorter person is the inorder predecessor.

       20
      /  \
    10    30
   /  \     \
  5   15    40
       
Inorder traversal: 5 -> 10 -> 15 -> 20 -> 30 -> 40
For node 20, inorder predecessor is 15 (largest smaller value).

Finding predecessor:
1. Go left once (to 10)
2. Go right as far as possible (to 15)
3. 15 is predecessor

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. 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 go right.

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

2

Foundation

Inorder Traversal Basics

Concept: Learn how inorder traversal lists BST nodes in ascending order.

Inorder traversal visits nodes in this order: left child, current node, right child. For BST, this means visiting nodes from smallest to largest value.

Result

Inorder traversal of BST gives a sorted list of all node values.

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

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 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, predecessor is one of the ancestors where current node lies in the right subtree.

Result

You can find the predecessor by checking left subtree or moving up ancestors.

Understanding that predecessor can be in ancestors or left subtree 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 the rightmost node in left 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 more right child. That node is the predecessor.

Result

For node 20 with left child 10, move right to 15. 15 is predecessor.

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

5

Intermediate

Finding Predecessor Without Left Subtree

🤔Before reading on: if a node has no left child, do you think the predecessor is always null? Commit to yes or no.

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

Move up the tree until you find a node which is right child of its parent. That parent is predecessor. If none found, predecessor is null (no smaller node).

Result

For node 15 with no left child, predecessor is 10 (ancestor). For node 5, no predecessor (null).

Understanding ancestor traversal helps find predecessor when left subtree is missing.

6

Advanced

Java Code to Find Inorder Predecessor

🤔Before reading on: do you think the code should handle both left subtree and ancestor cases? Commit to yes or no.

Concept: Implement a method that finds inorder predecessor by checking left subtree and ancestors.

class Node { int val; Node left, right, parent; Node(int v) { val = v; } } Node inorderPredecessor(Node node) { if (node.left != null) { Node pred = node.left; while (pred.right != null) pred = pred.right; return pred; } Node p = node.parent; while (p != null && node == p.left) { node = p; p = p.parent; } return p; }

Result

The method returns the correct predecessor node or null if none exists.

Combining subtree and ancestor logic in code covers all cases for predecessor.

7

Expert

Handling Edge Cases and Performance

🤔Before reading on: do you think predecessor search always takes O(h) time, where h is tree height? Commit to yes or no.

Concept: Predecessor search depends on tree height; unbalanced trees can degrade performance. Edge cases include nodes with no predecessor or root node.

In balanced BSTs, search is O(log n). In skewed trees, it can be O(n). Also, if parent pointers are missing, predecessor search requires extra traversal from root. Handling nulls and verifying parent links is important.

Result

Understanding performance helps optimize BST operations and avoid bugs in edge cases.

Knowing time complexity and edge cases prepares you for real-world BST usage and debugging.

Under the Hood

The inorder predecessor is found by exploiting BST properties: left subtree nodes are smaller, right subtree nodes are larger. If left subtree exists, the predecessor is the maximum node there (rightmost). If not, the predecessor is the nearest ancestor for which current node lies in the right subtree. This uses parent pointers or traversal from root to track ancestors.

Why designed this way?

This design leverages BST's sorted nature to find predecessor efficiently without scanning all nodes. Alternatives like full traversal are slower. Parent pointers simplify ancestor lookup but increase memory. The approach balances speed and memory use.

Node
 ├─ Left Subtree (smaller values)
 │    └─ Rightmost node here is predecessor if exists
 └─ Right Subtree (larger values)

If no left subtree:
  Move up ancestors until current node is right child
  That ancestor is predecessor

Flow:
[Node] --has left--> [Go left] --go right as far--> [Predecessor]
[Node] --no left--> [Go up ancestors] --find right child link--> [Predecessor or null]

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, not necessarily the immediate left child.

Why it matters: Assuming left child is predecessor causes wrong results, breaking tree operations like deletion.

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

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

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

Why it matters: Ignoring ancestors misses valid predecessors, causing bugs in traversal or search.

Quick: Does finding predecessor always take constant time? Commit yes or no.

Common Belief: Finding inorder predecessor is a constant time operation.

Reality: It depends on tree height; in worst case, it takes O(h) time where h is tree height.

Why it matters: Underestimating time complexity leads to inefficient code in large or skewed trees.

Expert Zone

1

In BSTs without parent pointers, finding predecessor requires starting from root, increasing complexity.

2

In threaded BSTs, predecessor pointers are stored explicitly, speeding up traversal but complicating insertion.

3

In balanced BSTs like AVL or Red-Black trees, predecessor search remains O(log n), but rotations can affect parent links.

When NOT to use

If you need constant time predecessor queries, use augmented data structures like threaded BSTs or balanced trees with explicit predecessor pointers. For unordered trees, inorder predecessor concept does not apply.

Production Patterns

In production, inorder predecessor is used in node deletion algorithms to replace deleted nodes with predecessor values. It also helps in range queries and nearest smaller value lookups in BST-backed databases or indexes.

Connections

Inorder Successor

Opposite concept in BST traversal sequence.

Understanding predecessor clarifies successor logic, as both rely on similar subtree and ancestor navigation.

Doubly Linked List

Both maintain ordered sequences with previous and next elements.

Knowing predecessor in BST is like knowing previous node in a doubly linked list, helping grasp bidirectional navigation.

Version Control Systems (Git)

Predecessor concept parallels finding previous commit in history.

Recognizing predecessor as 'previous state' helps understand how Git tracks changes and navigates commit history.

Common Pitfalls

#1 Assuming left child is always predecessor.

Wrong approach:

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

Correct approach:

if (node.left != null) {
Node pred = node.left;
while (pred.right != null) pred = pred.right;
return pred;
}

Root cause:

Misunderstanding that predecessor is the largest node smaller than current, not just immediate left child.

#2 Returning null if no left child without checking ancestors.

Wrong approach:

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

Correct approach:

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

Root cause:

Ignoring ancestor traversal for predecessor when left subtree is missing.

#3 Not handling null parent pointers leading to null pointer exceptions.

Wrong approach:

while (node.parent.val < node.val) node = node.parent; // no null check

Correct approach:

while (node.parent != null && node == node.parent.left) {
node = node.parent;
}

Root cause:

Not checking for null causes runtime errors in edge cases like root node.

Key Takeaways

The inorder predecessor is the node with the largest value smaller than the given node in a BST.

To find it, check the left subtree's rightmost node or move up ancestors where the node is in the right subtree.

Understanding predecessor helps in BST operations like deletion and traversal.

Handling edge cases and tree structure details ensures correct and efficient predecessor search.

Predecessor concept connects to many ordered data structures and real-world navigation problems.

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, so predecessor is the previous node in this order.

2. Step 2: Define inorder predecessor

   The inorder predecessor is the node with the largest value smaller than the current node's value.

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 just before current node 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 Java method signatures correctly represents a function to find the inorder predecessor in a BST node?

easy

A. public Node findInorderSuccessor(Node root, int key)

B. public int findInorderPredecessor(int[] arr, int key)

C. public Node findInorderPredecessor(Node root, int key)

D. public void findInorderPredecessor(Node root)

Solution

1. Step 1: Identify correct parameters for BST predecessor method

   We need the BST root and the key node value to find predecessor, so method should accept Node root and int key.

2. Step 2: Check method return type and name

   Return type should be Node (the predecessor node), and method name should indicate predecessor, so 'findInorderPredecessor(Node root, int key)' fits.

3. Final Answer:

   public Node findInorderPredecessor(Node root, int key) -> Option C

4. Quick Check:

   Correct signature includes root, key, returns Node [OK]

Hint: Method needs root and key, returns Node predecessor [OK]

Common Mistakes:

• Using array instead of BST Node
• Confusing predecessor with successor method name
• Wrong return type like void or int

3. Given the BST below and the code snippet, what will be the output?

    20
   /  \
 10   30
   
Node predecessor = findInorderPredecessor(root, 20);
System.out.println(predecessor != null ? predecessor.data : "null");

Assuming findInorderPredecessor is correctly implemented.

medium

A. null

B. 10

C. 30

D. 20

Solution

1. Step 1: Identify inorder predecessor of node 20 in BST

   Inorder predecessor is the largest node smaller than 20. Left subtree of 20 has node 10, which is smaller and largest in left subtree.

2. Step 2: Confirm output of print statement

   Predecessor node data is 10, so printed output is "10".

3. Final Answer:

   10 -> Option B

4. Quick Check:

   Largest smaller node than 20 is 10 [OK]

Hint: Predecessor is max in left subtree if left exists [OK]

Common Mistakes:

• Printing null when left subtree exists
• Confusing successor with predecessor
• Printing the node itself instead of predecessor

4. Consider this buggy Java method to find the inorder predecessor in a BST:

public Node findInorderPredecessor(Node root, int key) {
    Node predecessor = null;
    while (root != null) {
        if (key < root.data) {
            root = root.left;
        } else {
            predecessor = root;
            root = root.right;
        }
    }
    return predecessor;
}

What is the main issue with this code?

medium

A. It does not handle the case when the node has a left subtree

B. It incorrectly updates predecessor when key equals root.data

C. It causes infinite loop for some inputs

D. It returns the successor instead of predecessor

Solution

1. Step 1: Analyze traversal logic for predecessor

   The code moves left if key < root.data, else moves right and updates predecessor. But it never checks left subtree of the node itself.

2. Step 2: Identify missing left subtree handling

   If the node has a left subtree, the predecessor is the maximum node in that left subtree, which this code does not check.

3. Final Answer:

   It does not handle the case when the node has a left subtree -> Option A

4. Quick Check:

   Missing left subtree max check causes wrong predecessor [OK]

Hint: Check left subtree max for predecessor if it exists [OK]

Common Mistakes:

• Ignoring left subtree max node
• Confusing predecessor with successor logic
• Assuming predecessor is always ancestor

5. You have a BST and want to find the inorder predecessor of a node with value 15. The node has no left child. Which approach correctly finds the predecessor?

hard

A. Find the maximum node in the left subtree of 15

B. Return the right child of node 15

C. Return null because no left child exists

D. Traverse from root, keep track of last node with value less than 15

Solution

1. Step 1: Understand predecessor when no left child

   If node has no left child, predecessor is one of its ancestors with value less than node's value.

2. Step 2: Use traversal from root to track predecessor

   Traverse from root to node 15, keep updating predecessor to last node with value less than 15.

3. Final Answer:

   Traverse from root, keep track of last node with value less than 15 -> Option D

4. Quick Check:

   No left child means ancestor with smaller value is predecessor [OK]

Hint: Track last smaller ancestor when no left child [OK]

Common Mistakes:

• Returning null immediately if no left child
• Trying to find max in non-existent left subtree
• Returning right child mistakenly