BST Inorder Predecessor in DSA Typescript - 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 order (left-root-right). This predecessor is the largest value smaller than the node's value. Finding the inorder predecessor helps in many tree operations like deletion or navigation.

Why it matters

Without the concept of an inorder predecessor, it would be difficult to efficiently find the next smaller value in a BST, which is crucial for operations like deleting nodes or traversing the tree in sorted order. This would make tree operations slower and more complex, affecting performance in databases, file systems, and many applications relying on sorted data.

Where it fits

Before learning about inorder predecessors, you should understand what a Binary Search Tree is and how inorder traversal works. After mastering inorder predecessors, you can learn about inorder successors, 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 closest smaller value 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 (shorter side) and then find the tallest person there who is still shorter than the given person.

       20
      /  \
    10    30
      \     \
      15    40

Inorder traversal: 10 -> 15 -> 20 -> 30 -> 40
Inorder predecessor of 20 is 15 (largest smaller value)

Finding predecessor of 20:
- Go left to 10
- From 10, go right as far as possible to 15
- 15 is predecessor

Build-Up - 7 Steps

1

Foundation

Understanding BST Structure

Concept: Learn the basic structure and properties of a Binary Search Tree.

A BST is a 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. This property allows quick searching, insertion, and deletion.

Result

You can identify if a tree is a BST and understand how values are organized.

Understanding the BST property is essential because it guarantees sorted order during inorder traversal, which is the basis for finding predecessors.

2

Foundation

Inorder Traversal Basics

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

Inorder traversal visits the left subtree, then the current node, then the right subtree recursively. This results in visiting nodes in sorted order for BSTs.

Result

You can list all BST nodes in ascending order by inorder traversal.

Knowing inorder traversal order helps you understand why the predecessor is the node visited just before the current node.

3

Intermediate

Defining Inorder Predecessor

Concept: Understand what the inorder predecessor means in the context of BST traversal.

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

Result

You can identify the predecessor conceptually for any node in a BST.

Recognizing the predecessor as the previous node in sorted order connects traversal with node relationships.

4

Intermediate

Finding Predecessor When Left Child Exists

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

Concept: Learn how to find the predecessor when the node has a left subtree.

If the node has a left child, the predecessor is the rightmost node in that left subtree. This is because it is the largest value smaller than the node.

Result

You can find the predecessor by going left once, then right as far as possible.

Understanding this rule simplifies predecessor search by focusing on a subtree rather than the whole tree.

5

Intermediate

Finding Predecessor When No Left Child

🤔Before reading on: If a node has no left child, do you think the predecessor is in its right subtree or somewhere else? Commit to your answer.

Concept: Learn how to find the predecessor when the node has no left subtree.

If the node has no left child, the predecessor is one of its ancestors. Specifically, it is the nearest ancestor whose right child is also an ancestor of the node. You move up the tree until you find such an ancestor.

Result

You can find the predecessor by moving up the tree until you find a node smaller than the current node.

Knowing to move up the tree when no left child exists prevents searching irrelevant parts and ensures correct predecessor identification.

6

Advanced

Implementing Predecessor Search in Code

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

Concept: Combine the rules into a complete algorithm to find the inorder predecessor in a BST.

The algorithm checks if the node has a left child. If yes, it finds the rightmost node in the left subtree. If no, it moves up the parent chain until it finds an ancestor smaller than the node. The code uses a loop and conditional checks to implement this.

Result

You get a function that returns the inorder predecessor node or null if none exists.

Implementing both cases in code clarifies the full logic and prepares you for real-world BST operations.

7

Expert

Handling Edge Cases and Performance

🤔Before reading on: Do you think the predecessor always exists for every node? Commit to your answer.

Concept: Explore edge cases like the smallest node and analyze time complexity.

The smallest node in a BST has no predecessor, so the function returns null. The time complexity is O(h), where h is the tree height, because the search moves down or up the tree at most once per level. Balanced trees keep this efficient, but skewed trees degrade performance.

Result

You understand when predecessor search fails and how tree shape affects speed.

Recognizing edge cases and performance implications helps you write robust and efficient BST code.

Under the Hood

Internally, the BST stores nodes with pointers to left and right children and optionally to parents. Finding the inorder predecessor involves pointer traversal: either descending to the rightmost node of the left subtree or ascending through parent pointers until a suitable ancestor is found. This leverages the BST's sorted property and tree structure to avoid scanning the entire tree.

Why designed this way?

This approach uses the BST's inherent ordering to find predecessors efficiently without extra storage. Alternatives like storing explicit predecessor pointers increase memory and complexity. The chosen method balances simplicity, speed, and memory use, fitting well with recursive and iterative tree algorithms.

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

If no left subtree:
Current Node
 └─ Parent chain upwards
      └─ First ancestor where current node is in right subtree is predecessor

Myth Busters - 4 Common Misconceptions

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

Common Belief: Many think the inorder predecessor is simply 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: Mistaking the left child as predecessor leads to incorrect results, breaking tree operations like deletion or traversal.

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

Common Belief: Some believe that if there is no left child, the node has no predecessor.

Reality: If no left child exists, the predecessor is found by moving up to ancestors until a suitable one is found.

Why it matters: Ignoring ancestor search causes missing predecessors, leading to bugs in navigation and deletion.

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

Common Belief: People often assume every node has a predecessor.

Reality: The smallest node in the BST has no predecessor, so the result can be null.

Why it matters: Failing to handle this case causes null pointer errors or incorrect assumptions in algorithms.

Quick: Is the inorder predecessor always found by searching the entire tree? Commit to yes or no.

Common Belief: Some think you must scan the whole tree to find the predecessor.

Reality: The BST structure allows finding the predecessor by limited traversal, not scanning the entire tree.

Why it matters: Not leveraging BST properties leads to inefficient code and poor performance.

Expert Zone

1

In BSTs without parent pointers, finding the predecessor requires maintaining a stack or recursion to track ancestors.

2

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

3

In balanced BSTs, predecessor search remains O(log n), but in skewed trees, it can degrade to O(n), affecting performance.

When NOT to use

Avoid relying on inorder predecessor logic in non-BST trees or when parent pointers are unavailable and recursion/stack is not feasible. For general graphs or unordered trees, use other traversal or search methods.

Production Patterns

In production, inorder predecessor is used in BST node deletion algorithms to replace a node with its predecessor, maintaining BST properties. It also helps in range queries and iterator implementations that traverse BSTs in sorted order.

Connections

Inorder Successor in BST

Opposite concept; successor is the next larger node after the current one.

Understanding predecessor clarifies successor logic since both rely on similar traversal patterns but in opposite directions.

Doubly Linked List Navigation

Similar pattern of moving backward and forward between nodes.

Knowing predecessor in BST helps grasp bidirectional navigation in linked lists, as both involve finding previous or next elements efficiently.

Version Control Commit History

Predecessor conceptually matches the previous commit in a linear history.

Recognizing predecessor as the immediate prior element in a sequence connects tree traversal with how software tracks changes over time.

Common Pitfalls

#1 Assuming the left child is always the predecessor.

Wrong approach:

function findPredecessor(node) {
return node.left; // wrong: left child may not be predecessor
}

Correct approach:

function findPredecessor(node) {
if (node.left) {
let pred = node.left;
while (pred.right) pred = pred.right;
return pred;
}
// else handle ancestor case
}

Root cause:

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

#2 Not searching ancestors when no left child exists.

Wrong approach:

function findPredecessor(node) {
if (!node.left) return null; // wrong: ignores ancestor search
// ...
}

Correct approach:

function findPredecessor(node) {
if (!node.left) {
let parent = node.parent;
while (parent && node === parent.left) {
node = parent;
parent = parent.parent;
}
return parent;
}
// ...
}

Root cause:

Ignoring the BST property that predecessor can be an ancestor when no left subtree exists.

#3 Not handling the smallest node case.

Wrong approach:

function findPredecessor(node) {
// code assumes predecessor always exists
return someNode; // may cause errors if none
}

Correct approach:

function findPredecessor(node) {
// returns null if no predecessor
if (!node.left && !ancestorFound) return null;
// ...
}

Root cause:

Assuming every node has a predecessor without checking edge cases.

Key Takeaways

The inorder predecessor in a BST is the node with the next smaller value in sorted order.

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

If no left subtree exists, the predecessor is found by moving up to the nearest ancestor smaller than the node.

Not every node has a predecessor; the smallest node has none.

Understanding predecessor logic is essential for BST operations like deletion and traversal.