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.
691 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.class Node {
constructor(value, left = null, right = null) {
this.value = value;
this.left = left;
this.right = right;
}
}
const root = new Node(10,
new Node(5, new Node(2), new Node(7)),
new Node(15, new Node(12), new Node(20))
);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.function inorder(root) {
// TODO: iterative in-order traversal returning an array of values
}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.function search(root, target) {
// TODO: BST search
}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.function insert(root, value) {
// TODO: iterative BST insert
}