Traversal#
In the realm of data structures, a tree is a nonlinear, hierarchical structure consisting of nodes, which hold data, connected by edges, which define the relationship between the nodes. One of the most fundamental operations we can perform on a tree is traversal, which is the process of visiting each node in the tree exactly once in a specified order.
There are several common strategies for tree traversal, each with its own use cases and properties. Broadly speaking, these strategies fall into two categories:
Depth-First Traversal: In this approach, we explore as far as possible along each branch before backtracking. The three most common variants of depth-first traversal are:
Preorder Traversal: Visit the root node, traverse the left subtree, and finally traverse the right subtree.
Inorder Traversal: Traverse the left subtree, visit the root node, and finally traverse the right subtree. This strategy is used commonly in binary search trees as it visits the nodes in ascending order.
Postorder Traversal: Traverse the left subtree, traverse the right subtree, and finally visit the root node. This strategy is often useful for operations such as deleting or freeing nodes of a tree from memory.
Breadth-First Traversal (or Level Order Traversal): In this approach, we visit all the nodes of a level before going to the next level. This strategy is widely used in algorithms related to searching and more.
While these strategies cover the most common forms of tree traversal, it’s worth noting that trees are highly flexible structures, and these traversal methods can be adapted or combined to suit specific problems. As always, the right traversal method depends on the specific properties of the tree and the nature of the problem you’re trying to solve. Understanding the basics of each traversal method and the scenarios in which they’re most effective is a critical part of mastering tree-based algorithms.
Let’s consider our running example.
1tree_values: List[Union[int, None]] = [
2 1,
3 2,
4 3,
5 None,
6 None,
7 4,
8 5,
9 None,
10 None,
11 None,
12 6,
13 7,
14 8,
15 None,
16 None,
17 None,
18 9,
19 None,
20 None,
21]
22
23root = build_binary_tree_from_list_preorder(tree_values)
24lines = print_binary_tree(
25 root, node_info=lambda n: (str(n.value), n.left, n.right), is_top=False
26)
27print("\n".join(lines))
1 __/ \_ 2 6 / \ / \ 3 4 7 9 / / 5 8
Preorder Traversal#
See my write up on preorder traversal here.
Inorder Traversal#
Postorder Traversal#
Level Order Traversal#
Tips on Tree Recursion (Backtracking)#
In the context of recursion and the code you provided, when we say “return,” we are referring to the control flow returning to the previous level of the recursive call stack.
When a recursive function is called, it starts a new level or instance of the function with the new input. If the base case is not met (i.e., the tree is not empty in this case), it keeps on calling itself, creating new levels in the process. When it finally hits the base case (an empty tree), it doesn’t have any operations to perform, so it “returns” control back to the previous level of the function where it was called. This returning cascades back through the previous levels all the way to the first level (which was the first call to the recursive function), at which point the recursion ends.
In our specific code, return is used to stop the execution of the current
function and go back to the previous function call (the previous level in the
recursive call stack). When the root is an empty list ([]), the function hits
the base case and immediately returns without doing anything else. This is how
it knows to stop making new recursive calls for this branch and to go back to
the previous level of recursion, effectively “traversing back up” the tree.
This is a key aspect of recursion: you always have a condition that breaks the recursion, and when that condition is met, you return from the current level of recursion. Without a base case that halts the recursion, you’d have an infinite loop, or in the context of recursion, infinite recursive calls.