BST Inorder Predecessor in DSA Typescript - Build from Scratch

BST Inorder Predecessor

📖 Scenario: You are working with a Binary Search Tree (BST) that stores numbers. You want to find the inorder predecessor of a given node. The inorder predecessor is the node with the largest value smaller than the given node's value.Think of the BST as a family tree sorted by age, and you want to find the closest older sibling who is younger than a specific person.

🎯 Goal: Build a TypeScript program that creates a BST, sets a target value, finds the inorder predecessor of that value in the BST, and prints the predecessor's value or null if none exists.

📋 What You'll Learn

Create a BST with the exact nodes: 20, 10, 30, 5, 15, 25, 35

Create a variable targetValue set to 15

Write a function findInorderPredecessor that finds the inorder predecessor of targetValue in the BST

Print the predecessor's value or null if no predecessor exists

💡 Why This Matters

🌍 Real World

Finding inorder predecessors is useful in database indexing and navigation systems where you need to find the closest smaller value to a given key.

💼 Career

Understanding BST traversal and predecessor/successor logic is important for software engineers working on search algorithms, data indexing, and optimization problems.

1

Create the BST nodes

Create a class called TreeNode with val, left, and right properties. Then create the BST with nodes having values 20, 10, 30, 5, 15, 25, and 35 arranged correctly as a BST.

DSA Typescript

// Define TreeNode class and create BST nodes
// Your code here

Hint

Define a TreeNode class with val, left, and right. Then create nodes and link them to form the BST.

2

Set the target value

Create a variable called targetValue and set it to 15.

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

const root = new TreeNode(20);
root.left = new TreeNode(10);
root.right = new TreeNode(30);
root.left.left = new TreeNode(5);
root.left.right = new TreeNode(15);
root.right.left = new TreeNode(25);
root.right.right = new TreeNode(35);

// Create targetValue variable and set it to 15
// Your code here

Hint

Just create a constant named targetValue and assign it the number 15.

3

Write the function to find the inorder predecessor

Write a function called findInorderPredecessor that takes root of type TreeNode | null and target of type number. It should return the inorder predecessor node or null if none exists. Use BST properties to find the predecessor efficiently.

DSA Typescript

function findInorderPredecessor(root: TreeNode | null, target: number): TreeNode | null {
    let predecessor: TreeNode | null = null;
    let current = root;
    while (current !== null) {
        if (target <= current.val) {
            current = current.left;
        } else {
            predecessor = current;
            current = current.right;
        }
    return predecessor;
// Print the predecessor value or null

Hint

Use a loop to traverse the BST. Move left if target is less or equal to current node's value. Otherwise, update predecessor and move right.

4

Print the inorder predecessor value

Call findInorderPredecessor with root and targetValue. Print the predecessor's val if it exists, otherwise print null.

DSA Typescript

Hint

Call the function and print the predecessor's value if found, else print null.

Practice

1. What is the inorder predecessor of a node in a Binary Search Tree (BST)?

easy

A. The right child of the given node

B. The node with the largest value smaller than the given node

C. The left child of the given node

D. The node with the smallest value larger than the given node

Solution

1. Step 1: Understand inorder traversal in BST

   Inorder traversal visits nodes in ascending order of their values.

2. Step 2: Define inorder predecessor

   The inorder predecessor of a node is the node visited just before it in inorder traversal, which means it has the largest value smaller than the given node.

3. Final Answer:

   The node with the largest value smaller than the given node -> Option B

4. Quick Check:

   Inorder predecessor = largest smaller value [OK]

Hint: Predecessor is just before in sorted order [OK]

Common Mistakes:

• Confusing predecessor with successor
• Thinking predecessor is always left child
• Assuming predecessor is the parent node

2. Which TypeScript function signature correctly represents a method to find the inorder predecessor of a BST node?

easy

A. function findInorderPredecessor(root: TreeNode): void

B. function findInorderPredecessor(node: TreeNode): number

C. function findInorderPredecessor(root: TreeNode, node: TreeNode): TreeNode | null

D. function findInorderPredecessor(): boolean

Solution

1. Step 1: Identify required inputs and outputs

   To find the inorder predecessor, we need the BST root and the target node, and we return the predecessor node or null if none.

2. Step 2: Match function signature

   function findInorderPredecessor(root: TreeNode, node: TreeNode): TreeNode | null matches this: it takes root and node, returns TreeNode or null.

3. Final Answer:

   function findInorderPredecessor(root: TreeNode, node: TreeNode): TreeNode | null -> Option C

4. Quick Check:

   Correct inputs and output type [OK]

Hint: Function needs root, node, returns node or null [OK]

Common Mistakes:

• Missing root parameter
• Returning wrong type like number or boolean
• No parameters or void return type

3. Given the BST below and the node with value 15, what is the inorder predecessor?

       20
      /  \
    10    30
      \
      15

medium

A. 10

B. 15

C. 20

D. 30

Solution

1. Step 1: Perform inorder traversal around node 15

   Inorder traversal visits nodes in order: 10, 15, 20, 30.

2. Step 2: Find node before 15 in traversal

   The node before 15 is 10, so 10 is the inorder predecessor.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Predecessor of 15 = 10 [OK]

Hint: Predecessor is previous in sorted order [OK]

Common Mistakes:

• Choosing the node itself as predecessor
• Choosing parent node incorrectly
• Confusing predecessor with successor

4. Consider this TypeScript code snippet to find the inorder predecessor of a node in a BST:

function inorderPredecessor(root: TreeNode | null, node: TreeNode): TreeNode | null {
  let predecessor: TreeNode | null = null;
  while (root) {
    if (node.val <= root.val) {
      root = root.left;
    } else {
      predecessor = root;
      root = root.right;
    }
  }
  return predecessor;
}

What is the bug in this code?

medium

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

B. It incorrectly updates predecessor when node.val > root.val

C. It returns the successor instead of predecessor

D. It causes infinite loop when root is null

Solution

1. Step 1: Understand inorder predecessor logic

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

2. Step 2: Analyze code behavior

   The code only moves down from root to find predecessor by comparing values, missing the left subtree check for node.

3. Final Answer:

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

4. Quick Check:

   Left subtree check missing for predecessor [OK]

Hint: Check left subtree for predecessor first [OK]

Common Mistakes:

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

5. You want to find the inorder predecessor of a node with value 25 in this BST:

        40
       /  \
     20    60
    /  \  /  \
  10  30 50  70
       /
     25

Which steps correctly find the inorder predecessor of 25?

hard

A. Check left subtree of 25 (none), then move up to ancestors; predecessor is 50

B. Check left subtree of 25 (none), then move up to ancestors; predecessor is 30

C. Check left subtree of 25 (none), then move up to ancestors; predecessor is 10

D. Check left subtree of 25 (none), then move up to ancestors; predecessor is 20

Solution

1. Step 1: Check left subtree of node 25

   Node 25 has no left child, so no predecessor in left subtree.

2. Step 2: Move up to ancestors to find predecessor

   Ancestor nodes smaller than 25 are candidates; 20 is the closest smaller ancestor.

3. Final Answer:

   Check left subtree of 25 (none), then move up to ancestors; predecessor is 20 -> Option D

4. Quick Check:

   Predecessor found by ancestor smaller than node [OK]

Hint: If no left child, predecessor is nearest smaller ancestor [OK]

Common Mistakes:

• Choosing successor instead of predecessor
• Ignoring ancestors when left subtree is empty
• Picking wrong ancestor value