BST Inorder Predecessor in DSA Javascript - Execution Trace

Concept Flow - BST Inorder Predecessor

Start at root node

↓

Find node with given key

↓

Does node have left child?

No→Go up to ancestors

↓

Find ancestor where node is in right subtree

↓

Go to left child

↓

Go to rightmost node in left subtree

↓

This node is inorder predecessor

↓

Done

To find the inorder predecessor, first find the node. If it has a left child, go to that left subtree and find its rightmost node. Otherwise, move up ancestors until you find a node that is a right child of its parent.

Execution Sample

DSA Javascript

function inorderPredecessor(root, key) {
  let node = findNode(root, key);
  if (!node) return null;
  if (node.left) {
    let pred = node.left;
    while (pred.right) pred = pred.right;
    return pred;
  }
  let ancestor = root;
  let predecessor = null;
  while (ancestor !== node) {
    if (node.val > ancestor.val) {
      predecessor = ancestor;
      ancestor = ancestor.right;
    } else {
      ancestor = ancestor.left;
    }
  }
  return predecessor;
}

This code finds the inorder predecessor of a node with given key in a BST.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Visual State
1	Start at root	50	root points to 50	50
2	Find node with key=40	50	move left	50 -> 30 -> 40
3	Find node with key=40	30	move right	50 -> 30 -> 40
4	Node found	40	node = 40	50 -> 30 -> 40
5	Check if node has left child	40	node.left = 35	40 has left child 35
6	Go to left child	35	pred = 35	40 -> 35
7	Check right child of pred	35	pred.right = null	35 has no right child
8	Rightmost node in left subtree found	35	pred = 35	Inorder predecessor is 35
9	Return predecessor	35	return 35	Done
10	Exit	-	-	Predecessor found: 35

💡 Predecessor found as rightmost node in left subtree of node 40

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	Final
node	null	40	40	40	40	40
pred	null	null	null	35	35	35
ancestor	-	-	-	-	-	-
predecessor	null	null	null	null	null	null

Key Moments - 3 Insights

Why do we look for the rightmost node in the left subtree?

Because the inorder predecessor is the largest node smaller than the current node, which is the rightmost node in its left subtree, as shown in steps 6-8 in the execution_table.

What if the node has no left child? How do we find the predecessor?

We move up to ancestors until we find a node where the current node is in the right subtree. This is not shown in this example but is part of the code logic after step 8.

Why do we stop moving right when pred.right is null?

Because the rightmost node has no right child, so we have found the largest node in the left subtree, as shown in step 7.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the value of pred?

A 35

B 40

C 30

D null

💡 Hint

Check the 'Pointer Changes' and 'Node Visited' columns at step 6.

At which step does the algorithm confirm the inorder predecessor?

A Step 4

B Step 8

C Step 7

D Step 10

💡 Hint

Look for the step where 'Rightmost node in left subtree found' is noted.

If node 40 had no left child, what would the algorithm do next?

A Return null immediately

B Look for the rightmost node in the right subtree

C Move up ancestors to find a node where current node is in right subtree

D Return the root node as predecessor

💡 Hint

Refer to the concept_flow and code logic after checking left child.

Concept Snapshot

BST Inorder Predecessor:
- Find node with given key.
- If node has left child, go to left subtree's rightmost node.
- Else, move up ancestors to find a node where current node is in right subtree.
- That node is the inorder predecessor.
- Returns null if no predecessor exists.

Full Transcript

To find the inorder predecessor in a BST, start by locating the node with the given key. If the node has a left child, the predecessor is the rightmost node in that left subtree. If there is no left child, move up the tree to find an ancestor where the node lies in the right subtree. This ancestor is the predecessor. The execution table traces these steps with node visits and pointer changes, showing how the predecessor is found as node 35 for key 40 in this example.