# Trees and Hierarchical Storage

Computer Science I · Data Structures · https://tryals.app/learn/computer-science-i/trees-and-hierarchical-storage

## Hierarchical Structures

A **tree** stores data hierarchically with a single **root** node at the top. Every node has child nodes, each non-root node has one **parent**, and nodes with no children are **leaves**. Trees model naturally-nested data like file systems and org charts.

A **binary tree** restricts each node to at most two children. The **binary search tree (BST)** adds an **invariant**: for any node, all values in its **left subtree** are smaller, and its **right subtree** are greater. Searching means comparing and going left or right, discarding half the tree each step.

| Traversal | Order | BST Effect | Height Formula | Height Impact |
| --- | --- | --- | --- | --- |
| **In-order** | Left, Node, Right | Visits sorted values | $\approx \log_2 n$ | Balanced = $O(\log n)$ |
| **Pre-order** | Node, Left, Right | Root-first copy | $n$ (degraded) | Sorted insert = $O(n)$ |

## Balance and Operations

When a BST is **balanced**, its subtrees stay roughly equal in height, making search, insertion, and deletion $O(\log n)$ operations. Each operation walks a single path from root to leaf, where the tree's **height** is about $\log n$.

$$\text{balanced height} \approx \log_2 n$$

A **balanced** tree ensures logarithmic operations. **Common pitfall:** assuming a BST is always $O(\log n)$. Inserting already-sorted data **degenerates** the tree into a linked list of height $n$, making operations $O(n)$. Self-balancing trees (AVL, red-black) prevent this degradation.

## Practice questions

5 of this lesson's 10 practice questions, with answers. The full set is in the app.

### 1. A binary search tree has root 5. The root's left child is 3 and its right child is 8; node 3 has left child 2 and right child 4. Order the values as an in-order traversal visits them.

**Answer:**

1. 2
2. 3
3. 4
4. 5
5. 8

**Why:** In-order gives 2, 3, 4, 5, 8, the values in sorted order, which is the defining property of an in-order traversal of a BST. Visiting the root first would be pre-order and would give 5, 3, 2, 4, 8, which is not sorted; the difference is only where the node itself is visited.

Page: https://tryals.app/practice/computer-science-i/trees-and-hierarchical-storage/a-binary-search-tree-has-root-5-the-roots-left-child-is-3-and-its

### 2. Searching a balanced binary search tree of 1023 nodes takes at most 10 comparisons; scanning a list of the same values takes up to 1023. Why does the tree save so much, and what does the saving depend on?

A. From the tree storing values in sorted order, which a list cannot do.
B. From discarding half the remaining candidates at every comparison.
C. From the tree being stored in contiguous memory, which makes each comparison faster.
D. From the tree performing several comparisons simultaneously at each level.

**Answer:** B. From discarding half the remaining candidates at every comparison.

**Why:** One comparison at the root discards half the tree entirely — not examined and rejected, never visited — so the candidate set halves each step: 1023, 511, 255, down to 1 in ten. Cost tracks height, and a balanced tree's height is about log₂ n. Sorted order alone is not the mechanism: a sorted list scanned linearly still takes n steps, and the halving is what saves the work.

Page: https://tryals.app/practice/computer-science-i/trees-and-hierarchical-storage/searching-a-balanced-binary-search-tree-of-1023-nodes-takes-at-most

### 3. Inserting 1, 2, 3, 4, 5, 6, 7, 8 into an empty binary search tree in that order produces a tree of height 8 that behaves like a linked list.

**Answer:** True

**Why:** True. Every insertion goes right, so the tree degenerates into a right spine, search becomes O(n), the exact cost a BST exists to avoid. Sorted input is the worst case, and it is a common one. Self-balancing trees (AVL, red-black) exist precisely to rotate this back to O(log n).

Page: https://tryals.app/practice/computer-science-i/trees-and-hierarchical-storage/inserting-1-2-3-4-5-6-7-8-into-an-empty-binary-search-tree-in

### 4. A binary search tree built from sorted input degrades to a linked list, and the fix, AVL or red-black, adds rotations to every insert. Why accept that overhead?

A. Because it turns an average-case hope into a worst-case guarantee
B. Because balanced trees use less memory per node
C. Because rotations make insertion faster than in an unbalanced tree
D. Because unbalanced trees produce incorrect search results

**Answer:** A. Because it turns an average-case hope into a worst-case guarantee

**Why:** You are buying a guarantee, not average speed, sorted input is common rather than exotic, and an attacker can supply it deliberately. Paying a constant factor on every insert to remove an O(n) worst case is the same trade as randomised hashing against hash flooding.

Page: https://tryals.app/practice/computer-science-i/trees-and-hierarchical-storage/a-binary-search-tree-built-from-sorted-input-degrades-to-a-linked

### 5. Select every statement the lesson supports about binary search trees.

A. Self-balancing trees exist to keep the height logarithmic
B. An in-order traversal of a BST produces the values in sorted order
C. A BST guarantees O(log n) operations whatever the insertion order
D. Inserting already-sorted data degenerates the tree into a chain
E. The ordering invariant lets a search discard half the remaining tree at each step

**Answer:** A. Self-balancing trees exist to keep the height logarithmic; B. An in-order traversal of a BST produces the values in sorted order; D. Inserting already-sorted data degenerates the tree into a chain; E. The ordering invariant lets a search discard half the remaining tree at each step

**Why:** The invariant, the degeneration, the sorted traversal and the purpose of self-balancing trees are all stated. The false option is the guarantee: logarithmic cost holds only when the tree is balanced, and sorted input destroys that balance, asserting the guarantee unconditionally is the exact pitfall the lesson names.

Page: https://tryals.app/practice/computer-science-i/trees-and-hierarchical-storage/select-every-statement-the-lesson-supports-about-binary-search-trees