BST Inorder Predecessor in DSA Javascript - 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 of a node is the node with the next smaller value in the BST.Think of the BST as a family tree sorted by age, and you want to find the person who is just older than a given person but younger than everyone else older than them.

🎯 Goal: Build a program that creates a BST, sets a target node value, finds the inorder predecessor of that node, 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 called targetValue set to 15

Write a function called findInorderPredecessor that finds the inorder predecessor of the node with value targetValue

Print the value of the inorder predecessor or null if it does not exist

💡 Why This Matters

🌍 Real World

Finding inorder predecessors is useful in database indexing and navigation systems where you need to find the previous item in sorted order.

💼 Career

Understanding BST operations like inorder predecessor is important for software engineers working with search algorithms, data retrieval, and optimization.

1

Create the BST nodes and build the tree

Create a class called Node with a constructor that takes value and sets left and right to null. Then create the nodes with values 20, 10, 30, 5, 15, 25, and 35. Connect them to form the BST exactly as follows: 20 is root, 10 is left child of 20, 30 is right child of 20, 5 is left child of 10, 15 is right child of 10, 25 is left child of 30, and 35 is right child of 30.

DSA Javascript

// Create Node class and nodes
// Connect nodes to form the BST
// Your code here

Hint

Start by defining the Node class with value, left, and right. Then create each node and connect them as described.

2

Set the target node value

Create a variable called targetValue and set it to 15.

DSA Javascript

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

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

// Set the target node value
// 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 and targetValue as parameters. It should find the node with targetValue in the BST and return the value of its inorder predecessor node. If the node has a left subtree, the predecessor is the rightmost node in that left subtree. Otherwise, the predecessor is the last node for which the target node is in the right subtree. Return null if no predecessor exists.

DSA Javascript

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

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

const targetValue = 15;

// Write function findInorderPredecessor(root, targetValue) below
// Your code here

Hint

Use a loop to find the target node. Track the last node smaller than target as predecessor. If the target has a left child, find the rightmost node in that left subtree. Otherwise, return the tracked predecessor.

4

Print the inorder predecessor value

Print the result of calling findInorderPredecessor(root, targetValue). It should print the predecessor's value or null if none exists.

DSA Javascript

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

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

const targetValue = 15;

function findInorderPredecessor(root, targetValue) {
    let predecessor = null;
    let current = root;

    // Find the target node
    while (current !== null) {
        if (targetValue > current.value) {
            predecessor = current; // potential predecessor
            current = current.right;
        } else if (targetValue < current.value) {
            current = current.left;
        } else {
            // Node found
            break;
        }
    }

    if (current === null) {
        return null; // target not found
    }

    // If left subtree exists, find rightmost node there
    if (current.left !== null) {
        let temp = current.left;
        while (temp.right !== null) {
            temp = temp.right;
        }
        return temp.value;
    }

    // Otherwise, predecessor is the last node for which current is in right subtree
    return predecessor ? predecessor.value : null;
}

// Print the inorder predecessor value
// Your code here

Hint

Call findInorderPredecessor(root, targetValue) and print the result using console.log.

Practice

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

easy

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

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

C. The root node of the BST

D. The left child of the given node

Solution

1. Step 1: Understand BST ordering

   In a BST, left children are smaller and right children are larger than the node.

2. Step 2: Define inorder predecessor

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

3. Final Answer:

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

4. Quick Check:

   Inorder predecessor = largest smaller value [OK]

Hint: Inorder predecessor is largest smaller value [OK]

Common Mistakes:

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

2. Which of the following is the correct JavaScript function signature to find the inorder predecessor of a node in a BST?

easy

A. function findPredecessor(node) {}

B. function inorderSuccessor(root, node) {}

C. function findInorderPredecessor(root, node) {}

D. function getInorderPredecessor(node, root) {}

Solution

1. Step 1: Check function purpose and parameters

   The function should find the inorder predecessor given the BST root and the target node.

2. Step 2: Match signature to purpose

   function findInorderPredecessor(root, node) {} correctly uses root and node as parameters and names the function appropriately.

3. Final Answer:

   function findInorderPredecessor(root, node) {} -> Option C

4. Quick Check:

   Correct function name and parameters [OK]

Hint: Function needs root and node parameters [OK]

Common Mistakes:

• Using successor function name instead of predecessor
• Swapping parameter order
• Missing root parameter

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

       20
      /  \
    10    30
      \     \
      15     40

medium

A. 10

B. 15

C. 20

D. 30

Solution

1. Step 1: Locate node 15 and check left subtree

   Node 15 has no left child, so we look upwards to find the largest smaller ancestor.

2. Step 2: Find largest smaller ancestor

   Node 10 is the parent of 15 and smaller than 15, so 10 is the inorder predecessor.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Largest smaller value than 15 is 10 [OK]

Hint: If no left child, go up to largest smaller ancestor [OK]

Common Mistakes:

• Choosing the node itself as predecessor
• Choosing the parent if it is larger
• Confusing successor with predecessor

4. The following JavaScript code tries to find the inorder predecessor of a node in a BST but has a bug. What is the bug?

function findInorderPredecessor(root, node) {
  if (node.left) {
    let temp = node.left;
    while (temp.right) {
      temp = temp.right;
    }
    return temp;
  }
  let predecessor = null;
  let current = root;
  while (current) {
    if (node.val > current.val) {
      predecessor = current;
      current = current.right;
    } else {
      current = current.left;
    }
  }
  return predecessor;
}

medium

A. It does not handle the case when node has no left child

B. It does not check if node exists in the BST

C. It should return null if predecessor is not found

D. It incorrectly updates predecessor when node.val <= current.val

Solution

1. Step 1: Analyze code logic for predecessor

   The code correctly finds predecessor if node has left child or searches ancestors otherwise.

2. Step 2: Identify missing validation

   Code does not verify if the given node actually exists in the BST, which can cause incorrect results or errors.

3. Final Answer:

   It does not check if node exists in the BST -> Option B

4. Quick Check:

   Missing node existence check [OK]

Hint: Always verify node exists in BST before predecessor search [OK]

Common Mistakes:

• Assuming node is always in BST
• Confusing left child check logic
• Ignoring null return possibility

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

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

Which node is the inorder predecessor of 25, and why?

hard

A. 10, because it is the smallest node smaller than 25

B. 30, because it is the parent of 25

C. 25 has no inorder predecessor

D. 20, because it is the largest smaller ancestor

Solution

1. Step 1: Check if node 25 has left child

   Node 25 has no left child, so we look for the largest ancestor smaller than 25.

2. Step 2: Find largest smaller ancestor

   Ancestors of 25 are 30, 20, and 40. Among these, 30 is the parent of 25 and the largest smaller ancestor is 20, but since 25 is in the left subtree of 30, the inorder predecessor is 30's left subtree's rightmost node or the parent if no left subtree exists. Here, 25 is left child of 30, so predecessor is 20.

3. Final Answer:

   20, because it is the largest smaller ancestor -> Option D

4. Quick Check:

   Largest smaller ancestor = 20 [OK]

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

Common Mistakes:

• Choosing parent node 30 incorrectly
• Thinking no predecessor exists
• Choosing smallest smaller node instead of largest