Recall & Review
beginner
What is the inorder predecessor of a node in a Binary Search Tree (BST)?
The inorder predecessor of a node in a BST is the node that comes immediately before the given node in the inorder traversal of the BST. 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 subtree?
If the node has a left subtree, the inorder predecessor is the rightmost (maximum) node in that left subtree.
Click to reveal answer
intermediate
What if the node does not have a 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.
Click to reveal answer
intermediate
Why is the inorder predecessor important in BST operations?
The inorder predecessor helps in operations like deletion of a node in BST, where replacing the node with its inorder predecessor maintains the BST property.
Click to reveal answer
beginner
In C++, what is a simple approach to find the inorder predecessor of a given node in a BST?
Check if the node has a left child. If yes, find the rightmost node in the left subtree. Otherwise, traverse up using parent pointers until you find a node which is the right child of its parent. Return that parent.
Click to reveal answer
What is the inorder predecessor of the smallest node in a BST?
✗ Incorrect
The smallest node has no inorder predecessor because no node is smaller than it in the BST.
If a node has a left subtree, where is its inorder predecessor located?
✗ Incorrect
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?
✗ Incorrect
You move up the tree until you find a node which is the right child of its parent; that parent is the inorder predecessor.
Why do we use the inorder predecessor in BST node deletion?
✗ Incorrect
Replacing a deleted node with its inorder predecessor keeps the BST property intact.
Which traversal order is used to define the inorder predecessor?
✗ Incorrect
The inorder predecessor is defined based on the inorder traversal order.
Explain how to find the inorder predecessor of a node in a BST when the node has a left subtree.
Think about the largest value smaller than the node.
You got /3 concepts.
Describe the steps to find the inorder predecessor if the node has no left subtree.
Consider moving up until you find a node that is a right child.
You got /3 concepts.