You insert the integers 1, 2, 3, 4, 5 into a BST in that order. What is the time complexity of a subsequent search operation?
AO(log n), because a BST always organizes data for binary search
BO(n), because sorted insertions produce a degenerate tree with height n
CO(n log n), because the tree must be rebuilt before searching
DO(1), because the last inserted node is always the root
When you insert keys in sorted order, each new key is always larger than all existing keys, so it always extends the rightmost branch. The result is a straight chain leaning right — effectively a linked list — with height n = 5. A search must traverse this entire chain in the worst case, giving O(n) time. This is the critical vulnerability of unbalanced BSTs: the O(log n) guarantee only holds for a balanced tree, and basic BSTs provide no balancing mechanism.
Question 2 Multiple Choice
To delete a node with two children from a BST, you should replace it with which value?
AThe node's parent, then reattach both subtrees to the grandparent
BThe in-order successor (leftmost node of the right subtree) or in-order predecessor, then delete that successor
CThe root of the right subtree, discarding the left subtree to preserve the BST property
DThe average of the left and right children's keys
You cannot simply connect two subtrees to the parent — this would require a node to have three children and would violate the BST ordering property. The standard approach is to find the in-order successor (the smallest key in the right subtree) or in-order predecessor (the largest key in the left subtree). Copying that value into the deleted node preserves the BST property. The successor/predecessor is then deleted from its original location — it has at most one child, reducing to an easier deletion case.
Question 3 True / False
A BST containing 15 nodes typically supports search in O(log 15) steps.
TTrue
FFalse
Answer: False
BST performance depends on height, not just size. A 15-node BST has height between ⌊log₂ 15⌋ = 3 (perfectly balanced) and 14 (fully degenerate). If the 15 nodes were inserted in sorted order, the height is 14 and search takes O(n) in the worst case. The O(log n) guarantee only holds when the tree is balanced, which basic BSTs do not guarantee. Self-balancing variants like AVL trees maintain O(log n) height explicitly.
Question 4 True / False
An in-order traversal of a BST visits nodes in sorted (ascending) order.
TTrue
FFalse
Answer: True
This follows directly from the BST property: at every node, all left descendants are smaller and all right descendants are larger. In-order traversal visits left subtree, then root, then right subtree — which, by the BST property, always processes keys in ascending order. This is useful in practice: in-order traversal of a BST produces a sorted sequence in O(n) time.
Question 5 Short Answer
Why is insertion order the critical factor in BST performance, and what is the worst-case insertion pattern?
Think about your answer, then reveal below.
Model answer: BST performance is determined by tree height, and height is determined by insertion order. Each insertion walks from the root to a leaf, placing the new node where it belongs. If keys arrive in sorted (or reverse-sorted) order, each new key is always the largest (or smallest) so far, so it always extends the rightmost (or leftmost) chain. The tree degenerates into a linked list with height n, making all operations O(n). Random insertion order tends to produce a roughly balanced tree with O(log n) height on average, but this is not guaranteed.
This is why unbalanced BSTs are suitable for random data but dangerous for sorted or nearly-sorted data — a common real-world case. Self-balancing trees (AVL, red-black) fix this by performing rotations after insertions to maintain bounded height, sacrificing a constant overhead in exchange for worst-case O(log n) guarantees.