BST Inorder Successor in DSA Typescript - Execution Trace

Concept Flow - BST Inorder Successor

Start at root

↓

Find node with given key

↓

Does node have right child?

Yes→Go to right child

↓

Find leftmost node in right subtree

↓

Go up to ancestor where node is in left subtree

↓

Return this ancestor as inorder successor

The flow finds the node, then if it has a right child, successor is leftmost node in right subtree; else, go up to ancestor where node is in left subtree.

Execution Sample

DSA Typescript

function inorderSuccessor(root: TreeNode | null, p: TreeNode): TreeNode | null {
  let successor: TreeNode | null = null;
  let current = root;
  while (current) {
    if (p.val < current.val) {
      successor = current;
      current = current.left;
    } else {
      current = current.right;
    }
  }
  return successor;
}

Finds the inorder successor of node p in a BST by traversing from root and tracking potential successors.

Execution Table

Step	Operation	Current Node	Successor	Action	Visual State
1	Start at root	20	null	Compare p.val=14 with 20	20 / \ 10 30
2	p.val < current.val	20	20	Move left to 10	20 / \ 10 30
3	p.val > current.val	10	20	Move right to 15	20 / \ 10 30 \ 15
4	p.val < current.val	15	15	Move left to null	20 / \ 10 30 \ 15
5	current is null	null	15	Stop traversal	Final successor: 15

💡 Traversal ends when current becomes null; last recorded successor is 15.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
current	20	20	10	15	null	null
successor	null	null	20	20	15	15

Key Moments - 3 Insights

Why do we update successor only when p.val < current.val?

Because successor must be the smallest node greater than p; when p.val < current.val, current is a potential successor (see steps 2 and 4 in execution_table).

Why do we move right when p.val >= current.val?

Because nodes with values less or equal to p.val cannot be successors; we look for larger values on the right subtree (see steps 3 and 5).

What if the node p has a right child? How is successor found?

This code finds successor by traversal from root; if p has right child, successor is leftmost node in right subtree, which will be found by moving left when p.val < current.val (step 4).

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of successor after step 3?

A 20

B 15

C null

D 10

💡 Hint

Check the 'Successor' column in execution_table row for step 3.

At which step does current become null, ending the traversal?

A Step 2

B Step 4

C Step 5

D Step 3

💡 Hint

Look at the 'Current Node' column in execution_table to find when it is 'null'.

If p.val was 25 instead of 14, how would successor change after step 2?

A Successor would be 20

B Successor would be 30

C Successor would be null

D Successor would be 15

💡 Hint

Check the condition p.val < current.val at step 2 and how successor updates.

Concept Snapshot

BST Inorder Successor:
- Successor is next larger node after given node p.
- If p has right child, successor is leftmost node in right subtree.
- Else, successor is ancestor where p is in left subtree.
- Traverse from root, update successor when p.val < current.val.
- Stop when current is null; last successor recorded is answer.

Full Transcript

This visualization shows how to find the inorder successor of a node p in a binary search tree. Starting from the root, we compare p's value with the current node's value. If p's value is less, we record current as a potential successor and move left. If p's value is greater or equal, we move right. We continue until we reach null, then return the last recorded successor. The example traces finding successor of node with value 14 in a BST with root 20. The successor found is 15. Key points include updating successor only when p.val < current.val and moving right otherwise. This method works because BST properties guarantee the successor is the smallest node greater than p.