Binary Search Tree — Reasoning Check

Apply inherited bounds, sorted-order reasoning, and lazy iterator state.

Get every question correct to pass this checkpoint. You can review feedback, revise your answers, and submit again.

1. A proposed BST has root 20, left child 8, and right child 30. Node 8 has right child 15, and node 15 has right child 22. Every parent-child comparison appears valid. Which inherited constraint rejects the tree?

Select one answer.

A BST cannot have a right child inside a left subtree Every node below 8 must be less than 8 22 must be less than 20 because it remains in the root’s left subtree 22 must be less than 15 because it is a right child

2. A validator accepts any nondecreasing inorder sequence. On a tree with root 4, left leaf 2, and right leaf 4, why is that insufficient for this strict-BST contract?

Select one answer.

The sequence [2,4,4] is nondecreasing but not strictly increasing Duplicates are allowed only when they occur in a right subtree Inorder traversal is unrelated to BST validation The inorder sequence should be decreasing

3. Insert distinct values [12,5,19,2,9,15,21,7,11] into an empty BST. What value does KthSmallest return for k=6?

4. A BST has root 6, left leaf 2, and right child 14. Node 14 has left child 10, whose children are leaves 8 and 12. After Next returns 2, then 6, and HasNext is called twice, what does the next Next return?

5. A valid BST has root 50, left child 20 with right leaf 49, and right leaf 80. A minimum-difference routine checks only parent-child pairs. Which missed pair proves that approach wrong?

Select one answer.

20 and 49, whose difference is 29 49 and 50, whose difference is 1 20 and 80, whose difference is 60 50 and 80, whose difference is 30

6. A BST consists of root 1 with right child 9, followed by left-child chain 9→8→7→6. In the usual lazy iterator, which operation pushes the four nodes 9,8,7,6?

Select one answer.

The first Next call, after popping root 1 and before returning its value Constructor, because it always traverses every node No single operation: pushing must be spread across four Next calls The first HasNext call

Auto-advance on pass

Join Discord