Non-Linear Data Structures: Trees: quick revision, 15 bites

Trees: Hierarchical, Not Linear

Data doesn't have to be a straight line.

A **tree** is a non-linear data structure where elements (nodes) are arranged in a hierarchy — one root, branching into children, forming levels.

Takeaway. Trees trade linear simplicity for hierarchical speed — that's why databases and file systems rely on them.

Tree Vocabulary You Must Know

Speak tree language fluently.

Takeaway. Precise vocabulary is half the exam — root, leaf, depth, and height appear in almost every tree question.

Linear vs Non-Linear: Why Trees Exist

Arrays walk; trees branch.

Takeaway. Trees win when data has natural hierarchy or when fast search matters.

A Tree with n Nodes Has Exactly n−1 Edges

One less edge than nodes — always.

Every tree with $n$ nodes has exactly $n-1$ edges. This is the quickest way to verify whether a given graph is actually a tree.

Takeaway. If edges ≠ nodes − 1, it's not a tree — it's either disconnected or has a cycle.

The Three Core Tree Traversals

Visit every node — three different orders.

Traversal means visiting every node exactly once. The order depends on **when you process the root** relative to its subtrees.

Takeaway. Inorder on a BST gives sorted data — that's the single most tested traversal fact.

Inorder Traversal in Code

Three lines that sort a BST.

Takeaway. Recursion mirrors the tree's own structure — left, root, right is literally the code order.

Binary Tree vs Binary Search Tree

Two children vs two rules.

Takeaway. The BST ordering rule is what turns a plain binary tree into a searchable structure.

Don't Confuse Height with Depth

Same tree, opposite directions.

Takeaway. Depth goes down from root; height goes up from leaf — memorize the direction, not just the number.

Trees Are Everywhere You Look

Your computer is a forest of trees.

Takeaway. If data has hierarchy, a tree is almost always the right model.

Why Databases Love B-Trees

Billions of rows, milliseconds to find one.

A **B-tree** is a balanced multi-way tree where each node holds many keys. Its short height means fewer disk reads per lookup.

Takeaway. Balanced trees keep search fast at scale — that's the whole point of using them in databases.

The Traversal Question Almost Always Appears

One traversal question, guaranteed marks.

Takeaway. Traversal questions are free marks if you trace carefully — don't rush the order.

Remember Traversals with 'Root Position'

Where's the root? That's the name.

Takeaway. The prefix tells you exactly where the root sits — no memorizing needed.

Unbalanced Trees Kill Performance

A tree can secretly become a list.

Takeaway. A BST is only fast if it's balanced — sorted input is the classic trap.

The Most-Asked Tree Interview Question

Height, depth, and balance — know all three.

Takeaway. Master recursive height calculation — it unlocks half of all tree interview problems.

Always Handle the Empty Tree

The null check saves your code.

Takeaway. The base case isn't optional — it's what makes recursion on trees safe.