Source: UIUC Data Structures
Tags: binary tree, complete tree, perfect tree, NULL pointers, level-order, inorder, preorder, postorder, traversal, BFS, queue, tree properties
Difficulty: Intermediate Prerequisites: Basic tree terminology, BST Insert and Delete notes (Part 1).
Big picture
Before you can reason about the performance of tree algorithms, you need a firm grip on what binary trees actually guarantee structurally. This set of notes covers the core properties of binary trees (how many NULL pointers, what "complete" and "perfect" mean, and what is always true about nodes and children), then walks through every standard traversal: inorder, preorder, postorder, and level-order. Traversals show up in nearly every tree question on the exam, either directly ("give the inorder output") or as a tool for reconstructing a tree.
A binary tree with n nodes always has n + 1 NULL pointers. A complete tree fills levels top-to-bottom, left-to-right. A perfect tree has every level fully filled. The four traversals each visit every node in O(n) time but in different orders: inorder (left, root, right) gives sorted output for BSTs; preorder (root, left, right) prints the root first; postorder (left, right, root) prints the root last; level-order visits nodes breadth-first using a queue.
Binary tree
A tree in which every node has at most two children (left and right). In simple terms, each node can branch into at most two paths.
Complete binary tree
A binary tree where every level is fully filled except possibly the last, and the last level is filled left to right with no gaps. Think of it as filling seats in a theatre row by row, left to right, never skipping a seat.
Perfect binary tree
A binary tree where every internal node has exactly two children and all leaves are on the same level. In simple terms, every level is completely full with no empty spots anywhere.
NULL pointer
A pointer in a tree node that does not point to a child. Every node has two pointer slots (left and right); when a child is absent, that slot is NULL.
Level-order traversal (breadth-first)
Visiting nodes level by level, from top to bottom, left to right within each level. Uses a queue (FIFO). Think of it as reading a family tree generation by generation.
Inorder traversal
Recursively visit the left subtree, then the root, then the right subtree. For a BST, this produces nodes in ascending sorted order.
Preorder traversal
Visit the root first, then recursively visit the left subtree, then the right subtree. The root of any subtree always appears before its descendants.
Postorder traversal
Recursively visit the left subtree, then the right subtree, then the root. The root of any subtree always appears after all its descendants.
True properties (these always hold):
Every node has at most 2 children.
A node can have 0 children (it is a leaf).
Every non-empty binary tree has exactly 1 root node.
Every non-root node has exactly 1 parent.
Common false claim:
"Every binary tree has at least one node." This is false. The empty tree (zero nodes) is a valid binary tree.
Every node in a binary tree has 2 outgoing pointer slots, giving 2n total pointer slots for n nodes. Of these, exactly n − 1 point to actual children (each non-root node receives exactly one incoming pointer from its parent). The rest are NULL.
NULL pointers = 2n − (n − 1) = n + 1
Example: a tree with 357 nodes has 358 NULL pointers.
A complete tree with 17 nodes has a unique shape. Levels 0 through 3 are fully filled (1 + 2 + 4 + 8 = 15 nodes), and level 4 has the remaining 2 nodes, placed in the two leftmost positions.
Height = 4 (the longest root-to-leaf path has 4 edges). The number of nodes on level 4 is 2.
For a complete tree of height h, you need all levels 0 through h − 1 fully filled, plus at least 1 node on level h. Fully filled levels hold 2^0 + 2^1 + ... + 2^(h−1) = 2^h − 1 nodes. Add 1 for the minimum on the last level.
Minimum nodes = 2^h − 1 + 1 = 2^h
Example: a complete tree of height 4 needs a minimum of 2^4 = 16 nodes.
A perfect tree of height h has every level fully filled.
Total nodes = 2^(h+1) − 1
Example: a perfect binary tree of height 3 has 2^4 − 1 = 15 nodes. There is only one possible shape for a perfect tree of a given height.
Algorithm: inorder(left), print(root), inorder(right).
For a BST, inorder traversal prints all keys in sorted (ascending) order. This is because every left subtree contains only smaller keys (printed first), the root prints next, then the right subtree (all larger keys) prints last. The recursive nature ensures this holds for every subtree.
Sorted output from inorder is a defining consequence of the BST property.
Algorithm: print(root), preorder(left), preorder(right).
The root of any subtree always appears first in its portion of the output. This property is useful for reconstructing trees: the first element in a preorder sequence is always the root.
Algorithm: postorder(left), postorder(right), print(root).
The root of any subtree always appears last. If node X appears before node Y in a postorder traversal, and Y is an ancestor of X, then X's entire subtree was fully processed before Y was printed.
Algorithm: use a queue (FIFO). Enqueue the root. While the queue is non-empty, dequeue a node, print it, and enqueue its children (left first, then right).
Level-order traversal visits nodes breadth-first: all of level 0, then all of level 1, and so on.
Example tree with root 4, left child 6 (left child 22, right child 5), right child 7 (left child 9, right child 8 with left child 2):
Level 0: 4
Level 1: 6, 7
Level 2: 22, 5, 9, 8
Level 3: 2
Level-order output: 4, 6, 7, 22, 5, 9, 8, 2.
Note: within a level, left children are visited before right children because the queue preserves insertion order. However, if a question gives a tree where children could be ordered either way, both orderings within a level may be considered valid. (In standard binary trees, left-before-right is the convention.)
The queue operations step by step for the BST built from e, a, j, i, b, d, c, g, h, f:
Enqueue(e) → Queue: [e]
Dequeue(e) → print e → Enqueue(a), Enqueue(j) → Queue: [a, j]
Dequeue(a) → print a → Enqueue(b) → Queue: [j, b]
Dequeue(j) → print j → Enqueue(i) → Queue: [b, i]
Dequeue(b) → print b → Enqueue(d) → Queue: [i, d]
... and so on.
The last node to be enqueued depends on which node is the last leaf visited in breadth-first order.
Every traversal (inorder, preorder, postorder, level-order) visits each node exactly once and does O(1) work per node.
Time complexity = O(n) for any traversal of a tree with n nodes.
Given both the preorder and postorder traversal of a binary tree, you can deduce structural information:
The first element in preorder is always the root.
The last element in postorder is always the root.
If node X appears before node Y in postorder, and Y is an ancestor of X, then X must be in Y's subtree.
Preorder tells you roots of subtrees (they appear first). Postorder tells you which nodes are descendants (they appear before their ancestor).
Example: preorder 3, 1, 2, 10, 5, 4, 12 and postorder 2, 1, 4, 5, 12, 10, 3.
Root = 3 (first in preorder, last in postorder).
In preorder, 1 comes right after 3, so 1 is the root of 3's left subtree.
In postorder, 2 comes before 1, so 2 is a descendant of 1 (and since 1 is an ancestor of 2, node 1 has 2 in its subtree).
Level-order must have 3 first, then 1 and 10 at the next level.
Only valid level-order: 3, 1, 10, 2, 5, 12, 4.
Insufficient information warning: given only a preorder traversal (e.g. 1, 1, 2, 1, 1, 1) and its corresponding postorder (1, 1, 2, 1, 1, 1), there may be multiple valid tree shapes. In such cases, the level-order traversal cannot be uniquely determined.
Students often think inorder traversal of any binary tree gives sorted output. It only gives sorted output for a BST. For a general binary tree, inorder has no sorting guarantee.
Students confuse "complete" and "perfect." A complete tree allows a partially filled last level; a perfect tree requires every level to be fully filled.
Students sometimes think level-order traversal requires O(n log n) time. It is O(n), the same as every other standard traversal.
Students forget that the empty tree is a valid binary tree. The claim "every binary tree has at least one node" is false.
⚠️ The NULL pointer formula (n + 1) is a quick exam question. Memorise the derivation: 2n slots, n − 1 used, so n + 1 are NULL.
⚠️ Know the difference between complete and perfect trees and be able to draw both for a given height.
⚠️ Inorder traversal of a BST producing sorted output is frequently tested. Be ready to state why.
⚠️ Reconstructing trees from preorder + postorder traversals is a harder exam question. Practise identifying the root and subtree boundaries.
⚠️ Level-order traversal is tied to the queue data structure. Expect a question asking you to trace the queue state.
Fill in the blank: a binary tree with 100 nodes has ____ NULL pointers. 101.
True or false: a perfect binary tree of height 3 has 16 nodes. False. It has 2^4 − 1 = 15 nodes.
True or false: level-order traversal uses a stack. False. It uses a queue (FIFO).
Fill in the blank: inorder traversal visits the ____ subtree first, then the ____, then the ____ subtree. Left, root, right.
Q: How many NULL pointers does a binary tree with 357 nodes have?
A: 358. Formula: n + 1.
Q: What is the minimum number of nodes in a complete binary tree of height 4?
A: 16. All levels 0 through 3 must be full (15 nodes), plus at least 1 node on level 4.
Q: What data structure supports level-order traversal, and why?
A: A queue (FIFO). Nodes are processed in the order they were discovered, which naturally visits all nodes at one depth before moving to the next.
Q: Given a BST, what property does inorder traversal have?
A: It prints all keys in ascending sorted order. The left subtree (all smaller keys) is printed first, then the root, then the right subtree (all larger keys), recursively.
Q: If the preorder traversal of a BT is 3, 1, 2, 10, 5, 4, 12 and the postorder is 2, 1, 4, 5, 12, 10, 3, what is the level-order traversal?
A: 3, 1, 10, 2, 5, 12, 4.
Tree traversals are the basis for expression tree evaluation (covered in Part 3). Inorder gives infix notation, preorder gives prefix, and postorder gives postfix.
Complete binary trees are the underlying structure for binary heaps (used in heapsort and priority queues). Understanding the shape constraint of a complete tree is essential for heap analysis.
The NULL pointer count formula reappears in threaded binary trees, where those n + 1 NULL pointers are repurposed to point to inorder predecessors and successors, eliminating the need for a stack during traversal.
Related Terms / Search Tags binary tree properties, NULL pointers formula, complete binary tree, perfect binary tree, full binary tree, level-order traversal, breadth-first traversal, BFS tree, inorder traversal sorted, preorder traversal, postorder traversal, tree reconstruction, queue traversal, UIUC data structures exam 2