Trees
Beginner · 18 min read · Data Structures Basics, Trees, Heaps & Graphs
Vocabulary, the types of tree, binary search trees and the four traversals.
Arrays and lists are lines: every element has one before it and one after it. A tree branches: each element can have several "next" elements, its children. That shape fits anything hierarchical: folders, company org charts, HTML pages, the moves in a game. It also makes searching fast.
The vocabulary
Tree problems are full of these words. Step through them once:
How a tree is stored
In interviews a binary tree is a set of linked nodes, like a linked list with two next references:
Types of tree
Traversals: four ways to visit every node
The three depth-first orders are the same recursion. Only the position of the "visit" line changes:
Binary search trees
A BST adds one rule: left < node < right, at every node. Search then becomes a walk down one path:
Operations and their cost
The reference tests insert 0…99 in order into a plain BST and get a tree of height 100: sorted input turns a BST into a linked list. That's why real libraries use self-balancing trees.
In Java
Patterns that use trees
Interview questions
- What is the difference between a binary tree and a binary search tree?
- Why can BST operations become O(n), and how do libraries prevent it?
Further reading
Key takeaways
- A tree is nodes with children and no cycles; root, leaf, subtree, depth and height are the vocabulary.
- Binary, full, complete, perfect, balanced, degenerate, BST, n-ary, trie and heap are the types to know.
- Preorder, inorder and postorder differ only in when the node is visited; level order uses a queue.
- A BST orders values left < node < right, so operations are O(height): O(log n) only when balanced.
- In Java, TreeMap and TreeSet are balanced BSTs; interview trees are TreeNode objects you write yourself.