Binary Trees
Every node has at most two childrenA binary tree stores values in nodes, and every node has at most a left and a right child — there is no ordering rule like in a BST. Walk it in four different orders, then do the reverse: rebuild a tree from two of its traversals.
- Rootthe top node — no parent
- Leafa node with no children
- Traversala rule for visiting every node once
- Left part
- Root
- Right part
- Current
- In progress
- Visited / done
- New
Ready
Keyboard: ← → step · Space play / pause · R reset · Esc exit classroom mode
Every operation, in plain steps
These are exactly the steps the visualizer animates.
Words to know
The top node is the ROOT. A node's children hang below it; the node above is its PARENT. A node with no children is a LEAF. The DEPTH of a node is how many edges it is below the root, and the HEIGHT of the tree is the depth of its deepest leaf. In this lab you type a tree in level order, with - for an empty spot.
struct Node {
char data;
struct Node *left;
struct Node *right;
};
// A level order:
// / \ A, B, C, D, E, -, F
// B C
// / \ \ (- = no node here)
// D E F
Inorder
- Traverse the left subtree.
- Visit the node.
- Traverse the right subtree.
- For a BST this gives sorted order.
Preorder
- Visit the node first.
- Then the whole left subtree.
- Then the whole right subtree.
- The root is always the FIRST value.
Postorder
- Traverse the left subtree.
- Traverse the right subtree.
- Visit the node last.
- The root is always the LAST value.
Level order
- Put the root in a queue.
- Take the front node and visit it.
- Add its children at the rear.
- Repeat until the queue is empty.
Build: Preorder + Inorder
- The next value of preorder is the root.
- Find it in inorder.
- Values left of it form the left subtree, values right of it the right subtree.
- Repeat for the left part, then the right part.
Build: Postorder + Inorder
- Take roots from the END of postorder.
- Find each root in inorder to split it.
- Build the RIGHT part first…
- …because postorder read backwards is root, right, left.
Pseudocode
Language-independent steps. The visualizer shows the same logic in C, Python and Java.
How fast is each operation?
n = number of nodes, h = height. Recursive traversals use O(h) stack space; level order needs a queue as wide as the widest level. Building scans inorder for each root — storing inorder positions in a hash map makes it O(n).
| Operation | Best | Average | Worst | Speed |
|---|---|---|---|---|
| Inorder / Preorder / Postorder | O(n) |
O(n) |
O(n) |
Grows with n |
| Level order | O(n) |
O(n) |
O(n) |
Grows with n |
| Build from traversals (scan) | O(n log n) |
O(n log n) |
O(n²) |
Grows with n |
| Build from traversals (hash map) | O(n) |
O(n) |
O(n) |
Grows with n |
Which two traversals rebuild a tree?
| Traversals you have | Unique tree? | Why |
|---|---|---|
| Preorder + Inorder | Yes | Preorder gives the root, inorder splits left from right |
| Postorder + Inorder | Yes | Postorder gives the root (last), inorder splits left from right |
| Level order + Inorder | Yes | The first level-order value in each part is its root |
| Preorder + Postorder | Only for FULL trees | Without inorder, a lone child could be left or right |
| Just one traversal | No | Many different trees share it |
Every value must be different — with repeated values you cannot tell which copy is the root.
Special binary trees
| Type | Rule | Example use |
|---|---|---|
| Full | Every node has 0 or 2 children | Expression trees, Huffman trees |
| Complete | Every level full except the last, which fills from the left | Heaps (stored in an array) |
| Perfect | Every level completely full: 2^(h+1) − 1 nodes | Balanced reference shape |
| Skewed | Every node has only one child | Worst case: it is really a linked list |
Check your understanding
Answer each question — you will see the explanation straight away.
Preorder is A B D E C F. Which node is the root?
Preorder visits the node before its subtrees, so the very first value is always the root.
Postorder is D E B F C A. Which node is the root?
Postorder visits the node after both subtrees, so the root is always the last value.
Inorder is D B E A F C and the root is A. Which values are in the LEFT subtree?
In inorder everything left of the root belongs to its left subtree: D B E.
When building from postorder + inorder, why is the RIGHT subtree built first?
Postorder is left, right, root. Taking values from the end, you meet the root, then the right subtree's values, then the left subtree's.
Which pair of traversals can NOT always identify a unique binary tree?
Without inorder, a node with one child does not tell you whether it is a left or a right child (it works only for full binary trees).
Which data structure does a level order traversal use?
A queue (FIFO) makes sure every node on one level is visited before any node on the next level.
Trees quiz
Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.