Why BST Inorder Predecessor in DSA Typescript?

The Big Idea

Discover how to find the 'just before' value in a tree without checking every node!

The Scenario

Imagine you have a family tree drawn on paper, and you want to find the person who comes just before someone in the family order. Doing this by looking at every name and comparing takes a lot of time and can get confusing.

The Problem

Manually searching for the person just before another means checking many names one by one. This is slow and easy to make mistakes, especially if the tree is big or not sorted well.

The Solution

The BST Inorder Predecessor helps find the immediate previous value in a sorted tree quickly by following a clear path, avoiding unnecessary checks and mistakes.

Before vs After

✗ Before

function findPredecessor(root, target) {
  let values = [];
  inorderTraversal(root, values);
  for (let i = 1; i < values.length; i++) {
    if (values[i] === target) return values[i - 1];
  }
  return null;
}

✓ After

function findInorderPredecessor(root, target) {
  let predecessor = null;
  let current = root;
  while (current) {
    if (target > current.value) {
      predecessor = current;
      current = current.right;
    } else {
      current = current.left;
    }
  }
  return predecessor ? predecessor.value : null;
}

What It Enables

This lets you quickly find the closest smaller value in a sorted tree, making searches and updates much faster and more reliable.

Real Life Example

In a contact list sorted by names, finding the contact that comes just before a given name helps in quick navigation and suggestions.

Key Takeaways

Manual search is slow and error-prone for finding previous values.

BST Inorder Predecessor uses tree properties to find the answer efficiently.

This improves speed and accuracy in sorted data operations.