Why do we use a binary tree?

Arrays and linked lists put things in a line. A lot of the world isn't a line — it branches. And branching turns out to be the key to searching huge amounts of data in a handful of steps. Those are the two big reasons trees exist.

1. The world is full of hierarchies

Whenever things contain other things, you have a tree:

Three everyday trees. A file system: the folder Home contains Documents and Photos, and Documents contains cv.pdf and notes.txt. A web page: html contains head and body, and body contains h1 and p. An arithmetic expression: (2 + 3) times 4 is a tree with times at the root, plus on the left over 2 and 3, and 4 on the right.

File systems — folders inside folders.
The page you're reading — every web page is a tree of HTML elements (the DOM).
Compilers — your code is parsed into a *syntax tree*; (2 + 3) × 4 becomes the tree on the right, and evaluating it is a tree walk.
Decisions — a decision tree asks one yes/no question per node; a game AI explores a tree of possible moves.
Organisation charts, family trees, menus, comment threads…

Only trees with at most two children per node are *binary* trees, and many of these hierarchies have more. But binary trees are the ones interviews and data structure libraries are built on, and everything you learn here carries over.

Free account

Keep reading. It's free.

Sign up to read the rest of this lesson: 4 more sections, 3 drawings, a dry-run simulator and code in JavaScript, Python, Java and C++.

Still to come

2. Fast search: throw away half at every step
Height is everything
Why not a sorted array, or a hash table?
Key takeaways

Prev Next

Mark completed

Was this helpful?

Why do we use a binary tree?

1. The world is full of hierarchies

Keep reading. It's free.

Keep exploring