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.

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 key greater than the node's key.

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 key [OK]

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

Common Mistakes:

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

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

easy

A. function inorderSuccessor(node) {}

B. function inorderSuccessor(root, node) {}

C. function findSuccessor(root) {}

D. function successor(node, root) {}

Solution

1. Step 1: Identify required inputs

   To find the inorder successor, we need the BST root to traverse and the target node to find its successor.

2. Step 2: Match function signature

   function inorderSuccessor(root, node) {} correctly takes both root and node as parameters, enabling traversal and comparison.

3. Final Answer:

   function inorderSuccessor(root, node) {} -> Option B

4. Quick Check:

   Function needs root and node [OK]

Hint: Successor function needs both root and target node [OK]

Common Mistakes:

• Using only node without root
• Wrong parameter order
• Incorrect function naming

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

      20
     /  \
   10    30
     
     15

medium

A. 10

B. 30

C. 20

D. 15

Solution

1. Step 1: Locate node 15 and its right subtree

   Node 15 has no right child, so successor is an ancestor.

2. Step 2: Find the lowest ancestor whose left child is also ancestor of 15

   Node 20 is the first ancestor where 15 is in left subtree, so successor is 20.

3. Final Answer:

   20 -> Option C

4. Quick Check:

   Successor of 15 is 20 [OK]

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

Common Mistakes:

• Choosing right child when none exists
• Picking the node itself as successor
• Confusing successor with predecessor

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

function inorderSuccessor(root, node) {
  if (!root) return null;
  if (node.val >= root.val) {
    return inorderSuccessor(root.right, node);
  } else {
    let left = inorderSuccessor(root.left, node);
    return left ? left : root;
  }
}

What is the main issue with this code?

medium

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

B. It incorrectly compares node.val with root.val

C. It returns the node itself instead of successor

D. It causes infinite recursion

Solution

1. Step 1: Analyze code logic

   The code only traverses the tree comparing values but never checks if node has a right subtree.

2. Step 2: Identify missing right subtree check

   If node has a right child, successor is the leftmost node in right subtree, which this code ignores.

3. Final Answer:

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

4. Quick Check:

   Missing right subtree check causes wrong successor [OK]

Hint: Check right subtree first for successor [OK]

Common Mistakes:

• Ignoring right subtree
• Wrong base case
• Returning node instead of successor

5. You have a BST and want to find the inorder successor of node 25. The BST structure is:

        20
       /  \
     10    30
           /  \
         25    40

What is the inorder successor of node 25 and why?

hard

A. 40, because 40 is the right child of 30

B. 20, because it is the root

C. None, because 25 is the largest node in its subtree

D. 30, because 25 has no right child and 30 is the next bigger ancestor

Solution

1. Step 1: Check if node 25 has right subtree

   Node 25 has no right child, so successor is an ancestor.

2. Step 2: Find the lowest ancestor whose left subtree contains node 25

   Node 30 is the parent of 25 and is the next bigger node, so successor is 30.

3. Final Answer:

   30, because 25 has no right child and 30 is the next bigger ancestor -> Option D

4. Quick Check:

   Successor of 25 is 30 [OK]

Hint: If no right child, successor is nearest bigger ancestor [OK]

Common Mistakes:

• Choosing right child of parent instead of parent
• Assuming no successor if no right child
• Confusing root as successor