Trees — Chapter Quiz · Data Structures & Algorithms

Question 1

1

Which traversal of a valid BST visits nodes in ascending (sorted) order?

APre-order (root, left, right)BPost-order (left, right, root)CIn-order (left, root, right)DLevel-order (BFS)

In a BST, all left-subtree values are smaller than the root and all right-subtree values are larger. In-order traversal visits left → root → right, producing sorted output.

Question 2

2

BFS (level-order traversal) of a tree uses which data structure as its auxiliary?

AStackBQueueCPriority queue (min-heap)DHash map

BFS explores nodes level by level. A queue (FIFO) ensures you process nodes in the order they were discovered, advancing one depth level at a time.

Question 3

3

Deleting a node with two children from a BST replaces it with:

AThe root of the left subtreeBEither the in-order successor (smallest in right subtree) or in-order predecessor (largest in left subtree)CA null placeholderDThe parent node

Replacing a two-child node with its in-order successor (or predecessor) preserves the BST property. The successor is then deleted from the right subtree — it has at most one child, so deletion is straightforward.

Question 4

4

What is the difference between the depth of a node and the height of a tree?

AThey are the same conceptBDepth is the number of edges from the root to the node; height is the number of edges on the longest root-to-leaf pathCDepth counts nodes; height counts edgesDHeight is always twice the depth

Depth is measured downward from the root (root has depth 0). Height is measured upward from the deepest leaf (a leaf has height 0; the tree's height is the root's height).

Question 5

5

The Lowest Common Ancestor (LCA) of two nodes p and q in a BST can be found in O(h) time by:

ABFS from the root and tracking parent pointersBStarting at the root: if both p and q are smaller, go left; if both are larger, go right; otherwise the current node is the LCACBuilding an Euler tour and using a range-minimum queryDIn-order traversal and binary searching the result

In a BST, the first node where the paths to p and q diverge is the LCA. If both are to the left, descend left; if both to the right, descend right; otherwise you've found the split point.

Question 6

6

An AVL tree maintains balance by ensuring the heights of the left and right subtrees of every node differ by at most 1.

TTrueFFalse

The AVL balance factor = height(left) - height(right) ∈ {-1, 0, 1}. If an insertion or deletion breaks this invariant, rotations (single or double) restore it, keeping operations at O(log n).

Question 7

7

A complete binary tree with height h has between 2^h and ___ nodes.

A perfect binary tree of height h has exactly 2^(h+1) - 1 nodes. A complete tree fills all levels except possibly the last (filled left to right), giving a range of 2^h (minimum) to 2^(h+1) - 1 (maximum) nodes.

Question 8

8

Which of the following traversals can reconstruct a unique binary tree? (Select all that apply)

Select all that apply.

APre-order + In-orderBPost-order + In-orderCPre-order aloneDLevel-order + In-order

In-order combined with either pre-order, post-order, or level-order uniquely determines the tree structure (assuming no duplicate values). Pre-order alone is ambiguous — many trees share the same pre-order sequence.

Test what you learned.