Tree traversal is the process of visiting every node in a tree data structure in a specific order. This cheat sheet helps students compare the main traversal methods used in computer science, including depth-first and breadth-first approaches. It is useful for reading tree algorithms, tracing code, and solving interview-style or classroom problems.
Clear traversal rules make it easier to predict the output of recursive and iterative algorithms.
The core traversal orders are preorder, inorder, postorder, and level-order. Preorder visits the root before its subtrees, inorder visits the left subtree before the root in a binary tree, and postorder visits the root after its subtrees. Level-order visits nodes by depth using a queue.
Most tree traversals run in O(n) time because each node is visited once.
Key Facts
- Preorder traversal visits nodes in the order root, left subtree, right subtree.
- Inorder traversal for a binary tree visits nodes in the order left subtree, root, right subtree.
- Postorder traversal visits nodes in the order left subtree, right subtree, root.
- Level-order traversal visits nodes from top to bottom and left to right using a queue.
- A depth-first traversal explores as far as possible down a branch before backtracking.
- A breadth-first traversal visits all nodes at the current depth before moving to the next depth.
- For a tree with n nodes, preorder, inorder, postorder, and level-order traversal all have time complexity O(n).
- The recursive space complexity of depth-first traversal is O(h), where h is the height of the tree.
Vocabulary
- Tree
- A tree is a hierarchical data structure made of nodes connected by edges with one root node.
- Root
- The root is the top node of a tree and has no parent.
- Leaf
- A leaf is a node with no children.
- Traversal
- A traversal is a systematic process for visiting every node in a tree.
- Depth-first search
- Depth-first search visits nodes by going down a branch before returning to explore other branches.
- Breadth-first search
- Breadth-first search visits nodes level by level, usually with a queue.
Common Mistakes to Avoid
- Confusing preorder and postorder is a common mistake because both are depth-first traversals. Preorder visits the root first, while postorder visits the root last.
- Using inorder traversal on a general non-binary tree is usually wrong because inorder is defined for binary trees with left and right subtrees.
- Forgetting the queue in level-order traversal is incorrect because breadth-first traversal must process nodes in first-in, first-out order.
- Stopping after reaching a leaf is wrong because traversal must backtrack and continue until every node has been visited.
- Assuming traversal changes the tree is incorrect because standard traversal only reads or processes nodes without rearranging links.
Practice Questions
- 1 Given a binary tree with root A, left child B, right child C, B's children D and E, and C's right child F, list the preorder traversal.
- 2 Given the same tree, list the inorder and postorder traversals.
- 3 If a complete binary tree has 15 nodes, what is the time complexity of visiting every node with level-order traversal, and why?
- 4 Explain why a stack or recursion matches depth-first traversal, while a queue matches breadth-first traversal.
Understanding Tree Traversal Reference
A traversal is more than a way to print values. It gives an algorithm a controlled path through a connected structure. Trees do not have one natural next item as arrays do.
Each node can lead to children, so the algorithm needs rules for deciding where to go and when to return. In recursive depth first code, each function call handles one node. It performs any required action, then calls itself on child nodes.
The base case is an empty child reference. Reaching that reference stops the current branch safely. When the call returns, the program resumes at the parent and continues with the next unfinished child.
The call stack explains why recursive code can be short but still uses memory. Every unfinished function call is stored until its child calls finish. A balanced tree has a small height compared with its number of nodes, so the stack stays fairly shallow.
A badly skewed tree can look like a linked list. Its height then equals the number of nodes, which may cause a stack overflow in languages with limited recursion depth. An iterative depth first method avoids recursive calls by using an explicit stack.
The programmer pushes nodes that must be visited later, then pops the next node to process. The order of pushes matters because a stack removes the most recently added item first.
A queue behaves differently. It keeps track of nodes waiting at the edge of the explored area. When a node is removed, its children join the back of the queue.
This makes level based processing natural. It is useful for finding the nearest item in an unweighted tree, grouping nodes by depth, or modeling a family hierarchy one generation at a time. Queue memory can become large in a wide tree because many nodes on one level may wait together.
Thus, running time alone does not describe the full cost of an algorithm. Space use depends on tree shape and on the traversal method.
Traversal choice often follows the job being done. A preorder style walk can copy or serialize a tree because it records a parent before describing descendants. Postorder is useful when a parent depends on completed child results.
For example, a program can calculate the size of a folder tree or delete child files before removing their folder entry. Inorder has a special connection to binary search trees. If the search tree rule is maintained, an inorder walk produces keys in sorted order.
This does not mean every binary tree becomes sorted through inorder traversal. Students should trace small examples by drawing the tree, marking each visit, and recording stack or queue contents after every step. Pay close attention to null children, duplicate values, and whether the task asks for visiting, printing, searching, or modifying nodes.