BST Inorder Successor in DSA Javascript - Execution Trace

Concept Flow - BST Inorder Successor

Start at root node

↓

Find node with target value

↓

Does node have right child?

Yes→Go to right child

↓

Find leftmost node in right subtree

↓

Go up to parent while node is right child

↓

Return parent as successor or null if none

Find the node, then if it has right child, successor is leftmost node in right subtree; else go up to parent until node is left child.

Execution Sample

DSA Javascript

function inorderSuccessor(root, p) {
  if (p.right) {
    let curr = p.right;
    while (curr.left) curr = curr.left;
    return curr;
  }
  let succ = null;
  let curr = root;
  while (curr) {
    if (p.val < curr.val) {
      succ = curr;
      curr = curr.left;
    } else if (p.val > curr.val) {
      curr = curr.right;
    } else {
      break;
    }
  }
  return succ;
}

Finds the inorder successor of node p in BST by checking right subtree or climbing up ancestors.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start at root to find node 5	10	curr=root=10	10 / \ 5 15
2	Compare p.val=5 with curr.val=10	10	p.val < curr.val, succ=10, curr=curr.left=5	10 / \ 5 15
3	Compare p.val=5 with curr.val=5	5	p.val == curr.val, stop search	10 / \ 5 15
4	Check if node 5 has right child	5	No right child	10 / \ 5 15
5	Go up to parent while node is right child	5	curr=10, succ=10	10 / \ 5 15
6	p.val < curr.val, succ=10, curr=curr.left=5	5	Loop ends, successor=10	10 / \ 5 15
7	Return successor node	10	Return node with val=10	10 / \ 5 15
8	Exit	-	-	Successor found: 10

💡 Found successor node 10 after climbing up from node 5 with no right child.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
curr	root=10	10	5	5	5	10	5	null
succ	null	null	10	10	10	10	10	10
p.val	5	5	5	5	5	5	5	5

Key Moments - 3 Insights

Why do we check if the node has a right child first?

Because if the node has a right child, the successor is the leftmost node in that right subtree (see step 4 in execution_table). This is the simplest case.

Why do we climb up to the parent when there is no right child?

Because the successor is the lowest ancestor for which the node is in the left subtree (see steps 5 and 6). We keep moving up until we find such a parent or reach the root.

Why do we update 'succ' when moving left in the tree?

Because when p.val < curr.val, curr could be the successor, so we save it in 'succ' (step 2). If we move right, we do not update 'succ' because those nodes are smaller or equal.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the value of 'succ' after comparing p.val=5 with curr.val=10?

A null

B 5

C 10

D 15

💡 Hint

Check the 'Pointer Changes' column in step 2 of execution_table.

At which step does the algorithm determine that node 5 has no right child?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look for the step mentioning 'No right child' in the 'Pointer Changes' column.

If node 5 had a right child, how would the visual state change in the execution_table?

A We would find the leftmost node in the right subtree and return it immediately.

B We would climb up to the parent node as usual.

C We would return null because no successor exists.

D We would update 'succ' to the root node.

💡 Hint

Refer to the concept_flow where right child presence leads to leftmost node search.

Concept Snapshot

BST Inorder Successor:
- If node has right child, successor = leftmost node in right subtree.
- Else, climb up ancestors until node is left child of parent.
- Return that parent as successor or null if none.
- Uses BST property: left < node < right.
- Efficient O(h) time, h = tree height.

Full Transcript

To find the inorder successor of a node in a BST, first check if the node has a right child. If yes, the successor is the leftmost node in that right subtree. If no right child exists, move up the tree to find the lowest ancestor for which the node is in the left subtree. This ancestor is the successor. The process uses BST properties to efficiently find the next larger node. The execution trace shows starting at the root, searching for the node, checking right child, and climbing up parents if needed, finally returning the successor node or null.