Binary trees: height, traversals & counting
A binary tree has at most two children per node, distinguished as left and right. Its height bounds its capacity: a tree of height h has at most 2^(h+1) − 1 nodes, so n nodes force height at least ⌈log₂(n+1)⌉ − 1. The three depth-first traversals differ only in where the node itself is visited relative to its subtrees, and inorder on a binary search tree yields sorted output.
✓ Unlimited questions · marked criterion by criterion · no card needed
Method: how to approach it
The order below is what examiners expect to see, and each step carries its own marks.
- Preorder — node, left, rightVisit the node before descending. This is the order that reproduces the tree structure for serialisation.
- Inorder — left, node, rightOn a binary search tree this outputs the keys in increasing order.
- Postorder — left, right, nodeChildren before parents, which is what you need for deleting a tree or evaluating an expression tree.
- Count with Catalan numbersThe number of distinct binary tree shapes on n nodes is Cₙ = C(2n,n)/(n+1).
Worked example
For the tree with root 5, left child 3 (children 2 and 4) and right child 8, give the preorder, inorder and postorder traversals.
- Preorder: root first, then the whole left subtree, then the right: 5, then 3, 2, 4, then 8.
- Inorder: left subtree, root, right subtree. Left subtree inorder is 2, 3, 4.
- So inorder is 2, 3, 4, 5, 8 — sorted, confirming it is a binary search tree.
- Postorder: left subtree, right subtree, root: 2, 4, 3, 8, 5.
Answer. Preorder 5,3,2,4,8; inorder 2,3,4,5,8; postorder 2,4,3,8,5.
Where marks get dropped
These are the specific errors that cost credit on binary trees: height, traversals & counting questions — QED's rubric penalises each of them separately.
- Applying the traversal rule only at the root. Each rule is recursive and applies at every node.
- Confusing height counted in edges with height counted in nodes. State which convention you use — they differ by one.
- Assuming inorder determines the tree. Inorder alone does not; inorder plus preorder (or postorder) does.
Practise this until it is automatic
Unlimited fresh questions
QED generates new binary trees: height, traversals & counting problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.
Marked like an examiner
Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.
Answer in real notation
A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.
Saved to your library
Every question you generate is kept and re-takeable as a timed exam, and your Graphs mastery is tracked so you know when this is exam-ready.
Binary trees: height, traversals & counting — frequently asked questions
How many binary trees have n nodes?
The Catalan number Cₙ: 1, 1, 2, 5, 14, 42 for n = 0…5. The recurrence Cₙ = Σ Cₖ Cₙ₋₁₋ₖ comes from splitting at the root.
What is the minimum height for n nodes?
⌈log₂(n+1)⌉ − 1 edges, achieved by a complete tree. A degenerate tree that is really a path has height n − 1.
Which traversal reconstructs a tree?
No single one does. Preorder plus inorder, or postorder plus inorder, determines the tree uniquely — provided the keys are distinct.
The rest of Graphs
Terminology, connectivity, trees, paths and cycles. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Degrees & the handshake lemma
- 2Paths, cycles, connectivity & components
- 3Trees & their properties
- 4Bipartite graphs & colouring basics
- 5Euler & Hamilton paths and circuits
- 6Adjacency matrices & isomorphism
- 7Degree sequences & graphic sequences
- 8Spanning trees: Kruskal & Prim
- 9Shortest paths with Dijkstra
- 10Planarity & Euler’s formula
- 11Directed graphs, in-degree & out-degree
- 12Binary trees: height, traversals & counting
- 13Chromatic number & colouring bounds
- 14Matchings & Hall’s marriage theorem
Ready to make binary trees: height, traversals & counting exam-proof?
Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.
Start practising free →