BST Inorder Predecessor in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the inorder predecessor in a Binary Search Tree (BST)?

The inorder predecessor of a node in a BST is the node that comes immediately before it in the inorder traversal. It is the largest node smaller than the given node.

beginner

How do you find the inorder predecessor if the node has a left subtree?

If the node has a left subtree, the inorder predecessor is the rightmost (maximum) node in that left subtree.

intermediate

What if the node has no left subtree? How to find its inorder predecessor?

If the node has no left subtree, move up the tree using parent pointers until you find a node which is the right child of its parent. That parent is the inorder predecessor.

intermediate

Why is the inorder predecessor important in BST operations?

The inorder predecessor helps in operations like deletion in BST, where you replace a node with its inorder predecessor to maintain BST properties.

beginner

In TypeScript, what is a simple approach to find the inorder predecessor of a node in a BST?

Traverse to the left child, then keep moving right until no more right child exists. If no left child, use parent pointers to find the predecessor. This can be done with a loop and conditional checks.

What is the inorder predecessor of a node with a left subtree in a BST?

A The leftmost node in the right subtree

B The rightmost node in the left subtree

C The root node

D The parent node always

The inorder predecessor is the rightmost (maximum) node in the left subtree.

If a node has no left subtree, how do you find its inorder predecessor?

A Move up to the parent until the node is a right child

B Go to the right child

C Go to the left child

D There is no predecessor

You move up the tree until you find a node that is a right child of its parent; that parent is the predecessor.

Why is the inorder predecessor useful in BST deletion?

A It balances the tree

B It helps find the smallest node

C It deletes the root node

D It helps replace a node to maintain BST order

Replacing a node with its inorder predecessor maintains the BST property during deletion.

In inorder traversal, the predecessor of a node is:

A The previous node visited

B The next node visited

C The root node

D The leaf node

The inorder predecessor is the node visited immediately before the current node in inorder traversal.

Which of these is NOT true about inorder predecessor?

A It is always smaller than the node

B It can be found in the left subtree

C It is always the parent node

D It is the largest node smaller than the given node

The inorder predecessor is not always the parent; it depends on the tree structure.

Explain how to find the inorder predecessor of a node in a BST with and without a left subtree.

Think about the inorder traversal order and how predecessor relates to it.

Describe why the inorder predecessor is important when deleting a node from a BST.

Consider how BST properties must stay true after deletion.

Practice

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

easy

A. The right child of the given node

B. The node with the largest value smaller than the given node

C. The left child of the given node

D. The node with the smallest value larger than the given node

Solution

1. Step 1: Understand inorder traversal in BST

   Inorder traversal visits nodes in ascending order of their values.

2. Step 2: Define inorder predecessor

   The inorder predecessor of a node is the node visited just before it in inorder traversal, which means it has the largest value smaller than the given node.

3. Final Answer:

   The node with the largest value smaller than the given node -> Option B

4. Quick Check:

   Inorder predecessor = largest smaller value [OK]

Hint: Predecessor is just before in sorted order [OK]

Common Mistakes:

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

2. Which TypeScript function signature correctly represents a method to find the inorder predecessor of a BST node?

easy

A. function findInorderPredecessor(root: TreeNode): void

B. function findInorderPredecessor(node: TreeNode): number

C. function findInorderPredecessor(root: TreeNode, node: TreeNode): TreeNode | null

D. function findInorderPredecessor(): boolean

Solution

1. Step 1: Identify required inputs and outputs

   To find the inorder predecessor, we need the BST root and the target node, and we return the predecessor node or null if none.

2. Step 2: Match function signature

   function findInorderPredecessor(root: TreeNode, node: TreeNode): TreeNode | null matches this: it takes root and node, returns TreeNode or null.

3. Final Answer:

   function findInorderPredecessor(root: TreeNode, node: TreeNode): TreeNode | null -> Option C

4. Quick Check:

   Correct inputs and output type [OK]

Hint: Function needs root, node, returns node or null [OK]

Common Mistakes:

• Missing root parameter
• Returning wrong type like number or boolean
• No parameters or void return type

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

       20
      /  \
    10    30
      \
      15

medium

A. 10

B. 15

C. 20

D. 30

Solution

1. Step 1: Perform inorder traversal around node 15

   Inorder traversal visits nodes in order: 10, 15, 20, 30.

2. Step 2: Find node before 15 in traversal

   The node before 15 is 10, so 10 is the inorder predecessor.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Predecessor of 15 = 10 [OK]

Hint: Predecessor is previous in sorted order [OK]

Common Mistakes:

• Choosing the node itself as predecessor
• Choosing parent node incorrectly
• Confusing predecessor with successor

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

function inorderPredecessor(root: TreeNode | null, node: TreeNode): TreeNode | null {
  let predecessor: TreeNode | null = null;
  while (root) {
    if (node.val <= root.val) {
      root = root.left;
    } else {
      predecessor = root;
      root = root.right;
    }
  }
  return predecessor;
}

What is the bug in this code?

medium

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

B. It incorrectly updates predecessor when node.val > root.val

C. It returns the successor instead of predecessor

D. It causes infinite loop when root is null

Solution

1. Step 1: Understand inorder predecessor logic

   If node has a left subtree, predecessor is the rightmost node in that subtree, which this code does not check.

2. Step 2: Analyze code behavior

   The code only moves down from root to find predecessor by comparing values, missing the left subtree check for node.

3. Final Answer:

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

4. Quick Check:

   Left subtree check missing for predecessor [OK]

Hint: Check left subtree for predecessor first [OK]

Common Mistakes:

• Ignoring left subtree of node
• Assuming predecessor is always ancestor
• Confusing predecessor with successor logic

5. You want to find the inorder predecessor of a node with value 25 in this BST:

        40
       /  \
     20    60
    /  \  /  \
  10  30 50  70
       /
     25

Which steps correctly find the inorder predecessor of 25?

hard

A. Check left subtree of 25 (none), then move up to ancestors; predecessor is 50

B. Check left subtree of 25 (none), then move up to ancestors; predecessor is 30

C. Check left subtree of 25 (none), then move up to ancestors; predecessor is 10

D. Check left subtree of 25 (none), then move up to ancestors; predecessor is 20

Solution

1. Step 1: Check left subtree of node 25

   Node 25 has no left child, so no predecessor in left subtree.

2. Step 2: Move up to ancestors to find predecessor

   Ancestor nodes smaller than 25 are candidates; 20 is the closest smaller ancestor.

3. Final Answer:

   Check left subtree of 25 (none), then move up to ancestors; predecessor is 20 -> Option D

4. Quick Check:

   Predecessor found by ancestor smaller than node [OK]

Hint: If no left child, predecessor is nearest smaller ancestor [OK]

Common Mistakes:

• Choosing successor instead of predecessor
• Ignoring ancestors when left subtree is empty
• Picking wrong ancestor value