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.

Practice

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

easy

A. The node with the smallest key greater than the given node's key

B. The node with the largest key smaller than the given node's key

C. The root node of the BST

D. The left child of the given node

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits nodes in ascending order of their keys in a BST.

2. Step 2: Define inorder successor

   The inorder successor of a node is the next node visited after it in inorder traversal, which is the smallest node with a key greater than the current node.

3. Final Answer:

   The node with the smallest key greater than the given node's key -> Option A

4. Quick Check:

   Inorder successor = next bigger node [OK]

Hint: Inorder successor is next bigger node in sorted order [OK]

Common Mistakes:

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

2. Which of the following TypeScript function signatures correctly represents a function to find the inorder successor in a BST node?

easy

A. function inorderSuccessor(root: TreeNode | null, p: TreeNode): TreeNode | null

B. function inorderSuccessor(p: TreeNode): TreeNode

C. function inorderSuccessor(root: TreeNode): void

D. function inorderSuccessor(root: TreeNode, p: TreeNode): number

Solution

1. Step 1: Analyze parameters needed

   To find inorder successor, we need the BST root and the target node p.

2. Step 2: Analyze return type

   The function returns the successor node or null if none exists.

3. Final Answer:

   function inorderSuccessor(root: TreeNode | null, p: TreeNode): TreeNode | null -> Option A

4. Quick Check:

   Correct params and return type [OK]

Hint: Successor function needs root and target node, returns node or null [OK]

Common Mistakes:

• Missing root parameter
• Wrong return type (void or number)
• Not allowing null root

3. Given the BST below and the node with value 5, what is the inorder successor?

      6
     / \
    2   8
   / \   \
  0   4   9
     / \
    3   5

medium

A. Node with value 8

B. Node with value 6

C. Node with value 4

D. Node with value 9

Solution

1. Step 1: Locate node 5 and check right subtree

   Node 5 has no right child, so successor is one of its ancestors.

2. Step 2: Find lowest ancestor whose left child is ancestor of node 5

   Node 6 is the first ancestor where node 5 is in left subtree, so successor is node 6.

3. Final Answer:

   Node with value 6 -> Option B

4. Quick Check:

   Successor of 5 is 6 [OK]

Hint: If no right child, go up to first bigger ancestor [OK]

Common Mistakes:

• Choosing right child of root instead of ancestor
• Picking node 8 which is too big
• Confusing predecessor with successor

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

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

What is the bug in this code?

medium

A. It may cause infinite loop if root is null

B. It incorrectly updates the successor when p.val > root.val

C. It does not handle the case when node p has a right subtree

D. It returns the predecessor instead of successor

Solution

1. Step 1: Understand code logic

   The code moves down the tree to find the smallest node greater than p.val, updating successor accordingly.

2. Step 2: Identify missing case

   If p has a right subtree, the successor is the leftmost node in that subtree, but this code ignores that and only searches from root.

3. Final Answer:

   It does not handle the case when node p has a right subtree -> Option C

4. Quick Check:

   Right subtree check missing [OK]

Hint: Check right subtree first for successor [OK]

Common Mistakes:

• Ignoring right subtree of p
• Assuming successor always in ancestors
• Confusing successor with predecessor

5. You have a BST and want to find the inorder successor of a node p. The node p has a right child. Which of the following is the correct approach to find the inorder successor?

hard

A. Return the root of the BST

B. Return the rightmost node in p's left subtree

C. Return the parent of p

D. Return the leftmost node in p's right subtree

Solution

1. Step 1: Check if p has right subtree

   If p has a right child, the inorder successor is the smallest node in that right subtree.

2. Step 2: Find leftmost node in right subtree

   Traverse left children starting from p's right child until no more left child exists.

3. Final Answer:

   Return the leftmost node in p's right subtree -> Option D

4. Quick Check:

   Successor in right subtree's leftmost node [OK]

Hint: Successor with right child = leftmost node in right subtree [OK]

Common Mistakes:

• Returning parent instead of leftmost right subtree node
• Returning rightmost left subtree node
• Returning root regardless of p