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.
Click to reveal answer
beginner
How do you find the inorder predecessor if the node has a left child?
If the node has a left child, the inorder predecessor is the rightmost (maximum) node in the left subtree.
Click to reveal answer
intermediate
What if the node has no left child? How to find its inorder predecessor?
If the node has no left child, move up the tree using parent references until you find a node which is the right child of its parent. That parent is the inorder predecessor.
Click to reveal answer
intermediate
Why is the inorder predecessor important in BST operations?
It helps in operations like deletion of a node by replacing the node with its inorder predecessor to maintain BST properties.
Click to reveal answer
beginner
In inorder traversal, what is the order of nodes visited?
Inorder traversal visits nodes in ascending order: left subtree, current node, then right subtree.
Click to reveal answer
What is the inorder predecessor of a node with a left subtree?
✗ Incorrect
The inorder predecessor is the rightmost (maximum) node in the left subtree.
If a node has no left child, how do you find its inorder predecessor?
✗ Incorrect
You move up the tree until you find a node that is a right child of its parent; that parent is the predecessor.
In inorder traversal, nodes are visited in which order?
✗ Incorrect
Inorder traversal visits left subtree first, then current node, then right subtree.
Why do we use the inorder predecessor in BST deletion?
✗ Incorrect
Replacing the deleted node with its inorder predecessor maintains the BST property.
Which node has no inorder predecessor?
✗ Incorrect
The smallest node has no inorder predecessor because no smaller node exists.
Explain how to find the inorder predecessor of a node in a BST with and without a left child.
Think about the inorder traversal order and how predecessor relates to it.
You got /3 concepts.
Describe why the inorder predecessor is useful when deleting a node from a BST.
Consider how deletion affects BST ordering.
You got /3 concepts.