BST Inorder Predecessor in DSA Go - 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 smaller while the right child's value is larger than the node's value. 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 the next smaller element.

Why it matters

Without the concept of an inorder predecessor, it would be difficult to efficiently find the next smaller value in a BST or to correctly delete nodes while maintaining the BST properties. This concept allows quick navigation and manipulation of sorted data stored in a tree structure, which is essential in databases, file systems, and many algorithms.

Where it fits

Before learning about inorder predecessors, you should understand basic BST structure and inorder traversal. After mastering this, you can learn about inorder successors, 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 going 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 (shorter people) and find the tallest among them.

       20
      /  \
    10    30
      \     \
      15    40

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

Finding predecessor:
1. Go to left child (10)
2. From 10, go right as far as possible (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 in searching efficiently. Example: Node 20 Left child: 10 (smaller) Right child: 30 (larger)

Result

You can quickly decide where to go next when searching for a value in the tree.

Understanding the BST property is essential because it allows us to find values faster than scanning all nodes.

2

Foundation

Inorder Traversal Basics

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

Inorder traversal visits nodes in this order: left subtree, current node, right subtree. For BST, this means visiting nodes from smallest to largest. Example: Tree: 20 with left 10 and right 30 Inorder: 10 -> 20 -> 30

Result

You get a sorted list of all node values.

Knowing inorder traversal gives a natural way to see the sorted order of BST nodes.

3

Intermediate

Defining Inorder Predecessor

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

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

The inorder predecessor of a node is the largest node smaller than it. If the node has a left child, the predecessor is the rightmost node in the left subtree. If no left child, predecessor is one of the ancestors where the node lies in the right subtree.

Result

You can find the predecessor by either going left once and then right as far as possible, or by moving up the tree to find a suitable ancestor.

Understanding that the predecessor depends on subtree structure or ancestors helps in writing correct search logic.

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 inside the left subtree? Commit to your answer.

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

Start at the left child. Keep moving right until you can't go further. The last node you reach is the inorder predecessor. Example: Node 20 has left child 10, which has right child 15. Predecessor of 20 is 15.

Result

You find the largest smaller node efficiently by going left once and then right as far as possible.

Knowing to go right inside the left subtree ensures you find the closest smaller value, not just any smaller value.

5

Intermediate

Finding Predecessor Without Left Subtree

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

Concept: If no left child, predecessor is the nearest ancestor for which the node is in the right subtree.

Start from the node. Move up to its parent. Keep moving up while the node is the left child of its parent. The first parent where the node is a right child is the predecessor. Example: Node 15 has no left child. Its parent 10 is left child of 20. Keep moving up until you find a parent where node is right child.

Result

You find the predecessor by climbing up the tree to find a suitable ancestor.

Understanding ancestor traversal is key when left subtree is missing, preventing wrong assumptions.

6

Advanced

Implementing Predecessor in Go

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

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

type Node struct { Val int Left *Node Right *Node Parent *Node } func inorderPredecessor(node *Node) *Node { if node == nil { return nil } // Case 1: Left subtree exists if node.Left != nil { pred := node.Left for pred.Right != nil { pred = pred.Right } return pred } // Case 2: No left subtree, go up ancestors curr := node for curr.Parent != nil && curr == curr.Parent.Left { curr = curr.Parent } return curr.Parent }

Result

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

Separating cases in code mirrors the mental model and ensures correctness and clarity.

7

Expert

Handling Edge Cases and Performance

🤔Before reading on: Do you think the predecessor always exists for every node in a BST? Commit to yes or no.

Concept: Understand when predecessor does not exist and how to optimize traversal in large trees.

The smallest node in BST has no predecessor (returns nil). In large trees, storing parent pointers helps avoid extra searches. Without parent pointers, you must start from root to find ancestors, increasing complexity. Optimizations include caching predecessors or augmenting nodes with extra info.

Result

You can handle all cases correctly and write efficient code for real-world BSTs.

Knowing edge cases and performance tradeoffs prevents bugs and inefficiencies in production.

Under the Hood

The inorder predecessor is found by exploiting BST properties: left subtree nodes are smaller, right subtree nodes are larger. Internally, the algorithm either descends into the left subtree and moves right to find the maximum smaller node or climbs up the parent chain to find the nearest ancestor smaller than the node. Parent pointers or recursive calls help navigate the tree structure efficiently.

Why designed this way?

This method leverages the BST's sorted nature to avoid scanning the entire tree. Alternatives like scanning all nodes would be inefficient. Using left subtree maximum or ancestor traversal balances simplicity and speed. Parent pointers are added to avoid starting from root repeatedly, a tradeoff between memory and speed.

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

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

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 be deeper than the left child itself.

Why it matters: Assuming the left child is always the predecessor leads to incorrect results and bugs in tree operations.

Quick: If a node has no left child, does it have no predecessor? Commit yes or no.

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

Reality: The predecessor can be an ancestor node where the current node lies in the right subtree.

Why it matters: Ignoring ancestors causes failure to find predecessors, breaking algorithms like deletion.

Quick: Does every node in a BST have an inorder predecessor? Commit yes or no.

Common Belief: Every node in a BST has an inorder predecessor.

Reality: The smallest node has no predecessor; the function should return nil in this case.

Why it matters: Not handling this edge case causes runtime errors or incorrect behavior.

Quick: Can you find the predecessor without parent pointers efficiently? Commit yes or no.

Common Belief: Parent pointers are not needed to find the predecessor efficiently.

Reality: Without parent pointers, you must start from the root to find ancestors, which is less efficient.

Why it matters: Ignoring this leads to inefficient code that may degrade performance in large trees.

Expert Zone

1

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

2

Caching predecessor nodes or augmenting BST nodes with extra metadata can optimize repeated predecessor queries.

3

In threaded BSTs, predecessor pointers are stored explicitly, allowing O(1) access without traversal.

When NOT to use

Avoid using this approach in non-BST trees or when the tree is not binary. For balanced trees like AVL or Red-Black, specialized methods exist that maintain balance during predecessor queries. For very large datasets, consider B-trees or database indexes instead.

Production Patterns

In production, inorder predecessor logic is used in BST deletion algorithms to replace deleted nodes with their predecessor. It's also used in range queries and nearest smaller value searches. Parent pointers are often maintained for efficient upward traversal. Augmented BSTs may store subtree sizes or predecessor links for faster queries.

Connections

Inorder Successor in BST

Opposite concept

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

Doubly Linked List

Similar navigation pattern

The predecessor in BST is like the previous node in a doubly linked list, showing how tree traversal can mimic linear data structures.

Version Control Systems (Git)

Navigating history

Finding the inorder predecessor is like finding the previous commit in Git history, illustrating how tree navigation concepts apply in software versioning.

Common Pitfalls

#1 Assuming the left child is always the predecessor.

Wrong approach:

func inorderPredecessor(node *Node) *Node {
if node.Left != nil {
return node.Left
}
return nil
}

Correct approach:

func inorderPredecessor(node *Node) *Node {
if node.Left != nil {
pred := node.Left
for pred.Right != nil {
pred = pred.Right
}
return pred
}
// ancestor logic omitted for brevity
return nil
}

Root cause:

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

#2 Ignoring ancestor traversal when no left child exists.

Wrong approach:

func inorderPredecessor(node *Node) *Node {
if node.Left != nil {
// correct left subtree logic
}
return nil
}

Correct approach:

func inorderPredecessor(node *Node) *Node {
if node.Left != nil {
pred := node.Left
for pred.Right != nil {
pred = pred.Right
}
return pred
}
curr := node
for curr.Parent != nil && curr == curr.Parent.Left {
curr = curr.Parent
}
return curr.Parent
}

Root cause:

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

#3 Not handling the smallest node's predecessor (nil).

Wrong approach:

func inorderPredecessor(node *Node) *Node {
// code that always returns a node
}

Correct approach:

func inorderPredecessor(node *Node) *Node {
// code returns nil if no predecessor found
}

Root cause:

Failing to check for edge cases where no predecessor exists.

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, or by moving up ancestors if no left subtree exists.

Understanding the BST property and inorder traversal is essential to correctly find predecessors.

Parent pointers simplify finding predecessors by allowing upward traversal without starting from the root.

Edge cases like the smallest node having no predecessor must be handled to avoid errors.

Efficient predecessor finding is crucial for BST operations like deletion and nearest smaller value queries.