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.