Question Bank
Binary Search Tree Basics
Difficulty: Easy
Quick drills on the BST ordering invariant, in-order traversal yielding sorted output, and the most common search and insert operations.
Binary Search Tree Basics
Quick drills on the BST ordering invariant, in-order traversal yielding sorted output, and the most common search and insert operations.
690 views
13
State the BST ordering invariant in one sentence, then check whether the tree built below satisfies it. If not, name the offending node.
Examples
Example 1:
Input: tree 10 -> (5 -> (2, 7), 15 -> (12, 20))
Output: valid BST; in-order traversal = [2, 5, 7, 10, 12, 15, 20]
Explanation: For every node, all values in the left subtree are strictly less and all values in the right subtree are strictly greater. The sorted in-order traversal confirms the invariant.What does in-order traversal of a BST produce? Implement an iterative in-order traversal that returns the values as a list.
Examples
Example 1:
Input: BST 4 -> (2 -> (1, 3), 6 -> (5, 7))
Output: [1, 2, 3, 4, 5, 6, 7]
Explanation: In-order traversal visits left subtree, then node, then right subtree. For a BST this yields keys in ascending order. The iterative version uses an explicit stack to avoid recursion depth issues on skewed trees.Implement search(root, target) that returns the node holding target in a BST, or null if not present. What is the best-case and worst-case time complexity?
Examples
Example 1:
Input: BST 4 -> (2 -> (1, 3), 6), target = 3
Output: the node holding 3
Explanation: At each step compare target to root.value: 3 < 4 (go left), 3 > 2 (go right) finds the node holding 3. Best case O(log n) balanced, worst case O(n) on a chain.Example 2:
Input: BST 4 -> (2 -> (1, 3), 6), target = 5
Output: null
Explanation: The walk descends 5 > 4 (right) to 6, then 5 < 6 (left) into null, so the function returns null.Implement iterative insert(root, value) that inserts value into a BST and returns the (possibly new) root. Assume duplicates are not inserted (silently ignored).
Examples
Example 1:
Input: empty tree; insert 5, 3, 7, 1 in order
Output: root = 5; left subtree = 3 -> (1, null); right child = 7
Explanation: 5 becomes the root, 3 < 5 attaches as left child, 7 > 5 attaches as right child, 1 < 5 then 1 < 3 attaches as left child of 3.