Tree Traversals
Tree traversals dictate the exact sequence in which every node in a tree is visited, serving as the blueprint for serialization and evaluation.
Depth-First Strategies
Depth-First Search (DFS) on a binary tree explores as deeply as possible before backtracking. Depending on when we process the current node relative to its children, DFS yields three distinct traversal patterns: Pre-order, In-order, and Post-order.
Pre-order and Post-order
Pre-order traversal processes the node first, then the left child, then the right. This is ideal for copying a tree or serializing it. Post-order visits both children before processing the node itself, making it perfect for safely deleting nodes or evaluating abstract syntax trees.
Terms, operations, and practical uses
Depth-First Strategies
- Pre-orderProcess the current node, then traverse left, then traverse right. Excellent for deep-copying or serializing trees.
- In-orderTraverse left, process the node, then traverse right. Used primarily to extract sorted data from a BST.
- Post-orderTraverse left, traverse right, then process the node. Required for deleting trees or aggregating subtree values (like heights).
Breadth-First Strategies
- Level-orderProcesses all nodes at depth 0, then depth 1, etc. Implemented using a Queue instead of the call stack.
- Right-Side ViewA variation of level-order traversal where only the last processed node of each depth level is captured.
- Shortest PathIn unweighted tree structures, level-order traversal inherently discovers the shortest path from the root to any target.
Implementation Details
- Call StackRecursive DFS relies on the system call stack, making it vulnerable to StackOverflow errors on heavily degenerate trees.
- Iterative DFSDFS can be performed iteratively by manually pushing nodes onto a Stack, resolving recursion limit issues.
- Morris TraversalAn advanced O(N) time traversal that achieves O(1) space by temporarily modifying null leaf pointers to route back to ancestors.
Traverse a binary tree in inorder
def inorder(node):
if not node:
return
inorder(node.left)
print(node.val)
inorder(node.right)
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
visited = []
def inorder(node):
if not node:
return
inorder(node.left)
visited.append(node.val)
inorder(node.right)
inorder(Node(1, Node(2), Node(3)))
print('Visited: ' + ', '.join(str(v) for v in visited))void inorder(TreeNode* node, vector<int>& visited) {
if (!node) return;
inorder(node->left, visited);
visited.push_back(node->val);
inorder(node->right, visited);
}void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
System.out.print(node.val + " ");
inorder(node.right);
}root 1 with children 2 and 3Visited: 2, 1, 3Run the example step by step
In-order Traversal
In-order traversal visits the left child, processes the current node, and then visits the right child. When applied to a Binary Search Tree, this strategy naturally visits the elements in strictly ascending sorted order, flattening the hierarchy into a sequence.
Level-order Traversal
Level-order traversal uses Breadth-First Search (BFS) to visit all nodes at depth 0, then depth 1, and so on. Implemented using a queue rather than recursion, it is essential for finding the shortest path to a target or analyzing tree width.