Binary Tree Traversal

Traversing a binary tree is a fundamental operation that involves visiting all the nodes in the tree systematically. The structure of binary trees allows for several efficient traversal strategies, which are important for tasks such as searching, sorting, and modifying data within the tree. In this assignment, we will explore the two primary types of tree traversals: Depth-First Search (DFS) and Breadth-First Search (BFS), each useful for different scenarios depending on the nature of the problem you are solving.

Depth-First Search (DFS)

Depth-First Search (DFS) explores a binary tree by diving as deep as possible into the tree before backtracking. This traversal can be implemented either recursively or iteratively using a stack. There are three different DFS traversal strategies, Preorder, Inorder, and Postorder traversal. These traversal strategies determine the order in which nodes are "processed". "Processing" a node can involve various actions such as adding the node's value to an array, logging its value, or performing some computation. The difference between preorder, inorder, and postorder traversals lies in the position within the traversal steps where the node is processed—whether it happens before, between, or after visiting the subtrees.

The name of the traversal offers a clue about when the node processing occurs relative to the traversal of its subtrees.

We'll demonstrate each of these three DFS traversal strategies using the following binary tree:

Preorder Traversal

The prefix "pre" indicates that the processing of the node happens before its subtrees are traversed. In this example, the "processing" part will include adding the node's value to the result array.

To complete a preorder traversal, we can use a pattern, NLR, to help us remember how to traverse and process our nodes. N means processing the node, L means going to the left, and R means going to the right. Every time we reach a new node, we'll start NLR over again. When we've finished every step, N, L, and R, for every node, we'll have finished our preorder traversal. The walkthrough below visualizes preorder traversal using the tree we looked at above.

Step 1: We begin at the root node. Since N is the first letter in the pattern, we first process node 1 (N). For this demonstration, "processing" just means pushing the node's value into a result array.

Step 2: Next, we can move on to the L step. We check the left side of node 1, and find node 2. When we reach a new node, we'll start the NLR process over again. It's important to note that completing the NLR pattern for node 2 is a subprocess required to complete the L step for node 1. We'll indicate our active subprocess with a solid yellow circle, and our superprocesses that have yet to be completed with a dashed yellow line. Here, we are moving to node 2 as a subprocess to be able to complete step L of node 1.

Don't worry if this feels confusing now, follow along with the diagrams as we traverse our tree and these steps will become more clear.

Step 3: Starting fresh with our NLR process for node 2, we process the node and push it into our result array.

Step 4: Onto step L for node 2, except there is no left node, so we finish this step.

Step 5: Similarly, when we move to step R for node 2, there's no right node either. This means we've finished our entire NLR process for node 2 and we can go back to where we left off on node 1. By finishing this sub-tree, we've completed the L step for node 1.

Step 6: Having finished the L step, we move to step R on node 1. We check the right side of node 1 and we find node 3, beginning our NLR pattern over again for this node.

Step 7: We start by processing the node and push 3 into our result.

Step 8: For step L of node 3, we do find a node to the left. As a sub-step to completing the L step for node 3, we begin on node 4 with a new NLR pattern.

Step 9: We push 4 into our result.

Step 10: For step L of node 4, there is no left node.

Step 11: For step R, we do have a node to the right, so we start anew with NLR on node 5.

Step 12: We push 5 into our result.

Step 13: Step L of node 5 is simple, there is no left node.

Step 14: Step R is the same, as there is no right node from node 5. This completes our NLR pattern for node 5. We can return to the previous step we left off from. We came to node 5 as part of the R step for node 4.

Step 15: Completing our processing of node 5 means we've completed our R step for node 4. That completed our entire NLR pattern for node 4 and we can return to where we left off. We processed node 4 as part of the L step for node 3, so that's where we return to.

Step 16: Now that L is finished for node 3, we're onto the R step. There is no node to the right of node 3, meaning we've completed our NLR pattern for node 3. We can return to our previous step.

Step 17: Having completed the processing of node 3 and it's sub-nodes means that we've completed the R step of node 1, and every node in our tree has completed its NLR pattern, giving us our result array of [1, 2, 3, 4, 5].

Inorder Traversal

The prefix "in" indicates that the processing of the node (adding it to the array in this case) occurs in between the traversal of its left and right subtrees.

Let's explain the inorder traversal visually using the LNR pattern. The order is different, but L still stands for moving to the left child, N for processing the node, and R for moving to the right child. The logical steps we take will be very similar to the preorder traversal, but changing the order in which we take these steps will significantly change our result. At this point, you should hopefully be starting to feel comfortable with what these steps mean, so we'll keep the descriptions brief, but the walkthrough below still contains all of the visualized steps to an inorder traversal of our tree.

Step 1: Starting with our root node, node 1, we start with step L, moving us to node 2.

Step 2: At node 2, we start our LNR pattern over again. There isn't another node to the left.

Step 3: Step N on node 2 means we push our node's value into result.

Step 4: We finish node 2 with step R, but there's no node to the right. Now we can return back to node 1, having finished processing it's left subtree.

Step 5: Continuing on node 1 with our next step, N, we push 1 into result.

Step 6: Step R means we move to process the right subtree of node 1, our first stop being at node 3.

Step 7: Node 3 does have a node to its left, so we move to node 4. Remember, processing node 4 is part of the L step for node 3. Processing node 3 is a substep to step R of node 1.

Step 8: Step L of node 4 is brief, as there's no node to its left.

Step 9: Onto step N, we push 4 into result.

Step 10: Step R of node 4 leads us to node 5.

Step 11: Being a leaf node, node 5 doesn't have a node to the left.

Step 12: We process node 5 and push it into result.

Step 13: Node 5 doesn't have a right node. Finishing node 5, we can return to node 4, where we've finished step R.

Step 14: Finishing step R of node 4 means we've finished node 4 altogether and can return to node 3.

Step 15: Having finished the left subtree for node 3, we're onto step N, and we push 3 into result.

Step 16: Node 3 doesn't have a right node, so we can return back to node 1.

Step 17: Having finished the right subtree of node 1, we've finished our final LNR pattern for our root node and therefore have fully traversed our binary tree.

Postorder Traversal

The prefix "post" suggests that the processing (adding to the array) happens after its subtrees have been traversed. We'll use the same diagram style as before. You'll notice that every traversal type has about the same number of steps, with some variance for steps that require a bit more work to demonstrate visually. That makes sense considering that we aren't changing what nodes we do or don't process, we're just changing the order in which we move through our binary tree. Every node must be processed itself, have it's left subtree processed and have its right subtree processed.

Let's look at postorder traversal using the LRN pattern and our same tree in the walkthrough below:

Step 1: Just like the first step in our LNR pattern, we start by going to the left of our root node, node 1.

Step 2: At node 2, we can't go any further left. Put another way, we can't go any deeper into our tree.

Step 3: Given that node 2 is a leaf node, we also can't go any deeper to the right.

Step 4: After completing steps L and R, we can push the value of node 2 into our result. Because N is our final step in the LRN pattern, this finishes node 2 and we head back to node 1.

Step 5: We continue with the right subtree for our root node, taking us to node 3.

Step 6: Step L for node 3 takes us to node 4.

Step 7: Node 4 doesn't have a left node.

Step 8: Node 4 does have a right node, so we head to node 5.

Step 9: Being a leaf node, node 5 doesn't have a left node...

Step 10: ...or a right node.

Step 11: We can process node 5 and push its value into result. This finishes the whole pattern for node 5 and we go back to node 4.

Step 12: Having finished step R for node 4, we're ready to push 4 into our result. This finished the LRN pattern for node 4 and we can go back to node 3.

Step 13: Node 3 doesn't have a right node.

Step 14: We push 3 into our result and finish our LRN pattern for node 3, taking us back to our root.

Step 15: Having finished both the left and right subtrees for our root node, we can finally process our root node and finish our traversal by pushing 1 into result.

Breadth-First Search (BFS)

Breadth-First Search (BFS) is a traversal technique for trees and graphs that explores nodes level by level, starting from the root node and moving outward to all its direct children, then to their children, and so on. This method ensures that all nodes at a particular depth or distance from the root are visited before any nodes at the next level.

BFS uses a queue data structure to manage the order of node traversal. The queue helps process nodes in a FIFO (first-in, first-out) manner. We'll see this programmatically in the following assignments. Let's look at a few more diagrams that show what a BFS would look like with our tree. This walkthrough is much shorter, as BFS tends to be much easier to grasp.

Step 1: We first process the node at level 0, which is node 1.

Step 2: Then, we go to level 1 and process both nodes there 2 and 3.

Step 3: Next, we go to level 2 and process the node 4.

Step 4: Finally, we go to level 5 and process the node 5.