When should you use a binary tree?

There are two different questions hiding in "when do I use a tree?". One is about designing a program: when should your data *live* in a tree? The other is about interviews: the tree is given — which way should you *walk* it? This lesson answers both.

When your data belongs in a tree

It's hierarchical — things contain things: folders, menus, comments with replies, an organisation chart.
You need order and fast updates together — a sorted array searches fast but inserts slowly; a hash table is fast but unordered. A balanced binary search tree gives O(log n) for search, insert, delete *and* min/max/range queries.
You always need the smallest or largest item — a heap, a complete binary tree stored in an array, gives the minimum in O(1) and updates in O(log n).
You search by prefix — a trie (a tree of characters) powers autocomplete.
You're representing structure — expressions, syntax, decisions, game moves.

Free account

Keep reading. It's free.

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

Still to come

When a problem is a tree problem
When a tree is the wrong tool
Key takeaways

Prev Next

Mark completed

Was this helpful?

When should you use a binary tree?

When your data belongs in a tree

Keep reading. It's free.

Keep exploring