BST Inorder Predecessor in DSA Javascript - Deep Dive

Overview - BST Inorder Predecessor

What is it?

A Binary Search Tree (BST) is a tree where each node has up to two children, with left child values smaller and right child values larger than the node. The inorder predecessor of a node in a BST is the node that comes immediately before it when the tree is visited in sorted order (left-root-right). It helps find the closest smaller value to a given node.

Why it matters

Knowing the inorder predecessor helps in many tasks like deleting nodes, finding closest smaller values, or navigating the tree efficiently. Without this concept, operations on BSTs would be slower or more complex, making data retrieval and updates less efficient.

Where it fits

Before learning this, you should understand basic BST structure and inorder traversal. 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 largest node smaller than that node, found by looking left then right as far as possible.

Think of it like...

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

BST Example:

       20
      /  \
    10    30
   /  \     \
  5   15    40

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

Inorder predecessor of 20 is 15 (largest smaller value).

Finding predecessor:
- If node has left child, go left once, then right as far as possible.
- Else, go up to parent until node is right child.

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 order helps quickly find values by comparing and moving left or right.

Result

You can visualize a BST as a sorted structure where smaller values are always left, larger always right.

Understanding BST structure is essential because the inorder predecessor depends on this ordering to find the closest smaller node.

2

Foundation

Inorder Traversal Basics

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

Inorder traversal visits left subtree, then current node, then right subtree recursively. This produces nodes in ascending order for BSTs.

Result

For the BST: 20 with left 10 and right 30, inorder traversal outputs: 10 -> 20 -> 30

Knowing inorder traversal order helps understand why the predecessor is the node before in this 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 visited just before the current node in inorder traversal, not always 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 the nearest ancestor for which current node is in the right subtree.

Result

For node 20 in example, predecessor is 15 (rightmost in left subtree). For node 10, predecessor is 5 (rightmost in left subtree). For node 5, no predecessor (null).

Understanding the two cases for predecessor helps handle all nodes, even those without left children.

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 the 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 predecessor.

Result

For node 20, left child is 10. Moving right from 10 leads to 15, which has no right child. So predecessor is 15.

Knowing to go right as far as possible in 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 or can it be an ancestor? Commit to your answer.

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

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

Result

For node 15, no left child. Moving up, 15 is right child of 10, so predecessor is 10. For node 5, no left child and no such ancestor, so predecessor is null.

Understanding ancestor traversal prevents missing predecessors for nodes without left children.

6

Advanced

Implementing Predecessor in JavaScript

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

Concept: Implement a function that finds the inorder predecessor by checking left subtree first, else moving up ancestors.

function findPredecessor(node) { if (!node) return null; if (node.left) { let pred = node.left; while (pred.right) pred = pred.right; return pred; } let curr = node; while (curr.parent && curr === curr.parent.left) { curr = curr.parent; } return curr.parent || null; } // Example usage: // For node 20, returns node with value 15 // For node 5, returns null

Result

Calling findPredecessor on node 20 returns node 15; on node 5 returns null.

Separating cases in code matches the mental model and ensures correctness for all nodes.

7

Expert

Predecessor in BST Deletion Algorithm

🤔Before reading on: When deleting a node with two children, do you think replacing it with predecessor or successor is better? Commit to your answer.

Concept: In deletion, predecessor replaces the node to maintain BST properties. Understanding predecessor helps implement deletion correctly.

When deleting a node with two children: - Find inorder predecessor (largest smaller node). - Copy predecessor's value to node. - Delete predecessor node (which has at most one child). This preserves BST order. Example: Deleting 20 in example tree: - Predecessor is 15. - Replace 20's value with 15. - Delete node 15.

Result

After deletion, tree remains BST with correct order: 15 / \ 10 30 / \ 5 40

Knowing predecessor's role in deletion clarifies why it must be found efficiently and correctly.

Under the Hood

The BST stores nodes with pointers to left, right, and optionally parent. The inorder predecessor is found by either descending left subtree then rightmost path or ascending parent links until a right child relationship is found. This relies on BST's sorted structure and parent-child relationships to navigate efficiently without full traversal.

Why designed this way?

BSTs are designed for fast search, insert, and delete. Using inorder predecessor leverages the sorted order to find closest smaller nodes quickly. Alternatives like full traversal are slower. Parent pointers simplify upward navigation, avoiding extra memory or stack usage.

Finding predecessor:

  Node
   |
  Left Subtree?
   | Yes
   v
 Go left once, then right as far as possible
   |
  Predecessor found

   No
   |
  Move up parents until node is right child
   |
  Parent is predecessor or null if none

Myth Busters - 4 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 not be the immediate left child.

Why it matters: Assuming left child is predecessor causes wrong results, especially when left child has its own right subtree.

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: The predecessor can be an ancestor node where the current node is in the right subtree.

Why it matters: Ignoring ancestors misses valid predecessors, leading to incorrect tree operations.

Quick: Does the inorder predecessor always exist for every node except the smallest? Commit yes or no.

Common Belief: Every node except the smallest has an inorder predecessor.

Reality: The smallest node has no predecessor; all others do.

Why it matters: Confusing this can cause errors in boundary cases like minimum node handling.

Quick: Is it faster to find predecessor by full inorder traversal than using BST properties? Commit yes or no.

Common Belief: Full inorder traversal is simpler and just as fast to find predecessor.

Reality: Using BST properties and parent pointers is faster and more efficient than full traversal.

Why it matters: Using full traversal wastes time and resources, especially in large trees.

Expert Zone

1

Parent pointers simplify predecessor search but increase memory; some BSTs omit them and require stack or recursion.

2

In threaded BSTs, predecessor links are stored explicitly to speed up traversal without recursion or stack.

3

Predecessor logic is symmetric to successor logic but subtle differences in edge cases can cause bugs if not carefully handled.

When NOT to use

In balanced BST variants like AVL or Red-Black trees, specialized deletion and traversal methods may optimize or alter predecessor usage. For non-BST trees or heaps, predecessor concept does not apply; use other navigation methods.

Production Patterns

In production, predecessor is used in database indexing, memory allocators, and file systems to quickly find closest smaller keys. Efficient predecessor search enables fast range queries and ordered data manipulation.

Connections

Inorder Successor

Opposite concept; successor is next larger node after current in inorder traversal.

Understanding predecessor clarifies successor logic since both rely on similar tree navigation patterns.

Doubly Linked List

Both have 'previous' and 'next' elements; predecessor is like 'previous' node in sorted order.

Knowing predecessor helps understand bidirectional navigation in linked structures.

Version Control Systems (Git)

Finding predecessor commits in history is similar to finding inorder predecessor in commit trees.

Understanding tree navigation in BSTs aids grasping commit ancestry and branching in Git.

Common Pitfalls

#1 Assuming left child is always predecessor.

Wrong approach:

function findPredecessor(node) {
return node.left;
}

Correct approach:

function findPredecessor(node) {
if (node.left) {
let pred = node.left;
while (pred.right) pred = pred.right;
return pred;
}
let curr = node;
while (curr.parent && curr === curr.parent.left) {
curr = curr.parent;
}
return curr.parent || null;
}

Root cause:

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

#2 Ignoring ancestor traversal when no left subtree.

Wrong approach:

function findPredecessor(node) {
if (node.left) {
// correct left subtree logic
} else {
return null;
}
}

Correct approach:

function findPredecessor(node) {
if (node.left) {
let pred = node.left;
while (pred.right) pred = pred.right;
return pred;
}
let curr = node;
while (curr.parent && curr === curr.parent.left) {
curr = curr.parent;
}
return curr.parent || null;
}

Root cause:

Not realizing predecessor can be an ancestor when left subtree is missing.

#3 Not handling null or root node cases.

Wrong approach:

function findPredecessor(node) {
let pred = node.left;
while (pred.right) pred = pred.right;
return pred;
}

Correct approach:

function findPredecessor(node) {
if (!node) return null;
if (node.left) {
let pred = node.left;
while (pred.right) pred = pred.right;
return pred;
}
let curr = node;
while (curr.parent && curr === curr.parent.left) {
curr = curr.parent;
}
return curr.parent || null;
}

Root cause:

Not checking for null nodes or nodes without left subtree causes runtime errors or wrong results.

Key Takeaways

The inorder predecessor of a BST node is the largest node smaller than it, found by left subtree's rightmost node or ancestor traversal.

Understanding predecessor requires knowing BST structure and inorder traversal order deeply.

Predecessor is crucial for efficient BST operations like deletion and navigation.

Handling both cases--left subtree and ancestor--is essential for correct predecessor implementation.

Misconceptions about predecessor lead to bugs; careful mental modeling and code separation prevent errors.