There are two main ways of traversing a binary tree: breadth-first and depth-first. With breadth-first traversal, we begin traversing at the top of the tree’s root node, displaying its value and continuing the process with the left child node and the right child node. Descend a level and repeat this step until we finish displaying all the child nodes at the deepest level from left to right.
With depth-first traversal, we always traverse down each left-side branch of a tree fully before proceeding down the right branch. However, there are three traversal options:
- Preorder is when we perform an action on the current node first, followed by its left child node and its right child node
- Inorder is when we perform an action on the left child node first, followed by the current node and the right child node
- Postorder is when we perform an action on the left child node first, followed by the right child node and then the current node
For this lesson, we will implement the inorder traversal option. The advantage of this option is that the values are displayed in sorted order from the smallest to the largest value.
To illustrate, let’s say we have a binary tree that looks like this:
15
/------+-----\
12 20
/ \ / \
10 13 18 22
/ \ / \ / \ / \
8 11 12 14 16 19 21 25We begin by traversing the left subtree at each level, which brings us to the nodes with values 8, 10, and 11. The inorder traversal would be:
8, 10, 11We ascend one level up to visit root node 12 before we descend back to the bottom where the right subtree of 12, 13, and 14 resides.
Inorder traversal then continues with the values:
12, 12, 13, 14We again ascend one level up to visit root node 15 before we traverse the right subtree starting at the bottom level again. We continue with the bottom leftmost subtree where 16, 18, and 19 reside. The inorder traversal continues with:
15, 16, 18, 19We ascend one level up to visit root node 20 before we descend back to the bottom where the rightmost subtree containing nodes with values 21, 22, and 25 resides.
Traversal finishes with:
20, 21, 22, 25The entire inorder traversal becomes:
8, 10, 11, 12, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 25Notice that all the values displayed are sorted in ascending order.
Now let’s implement this inorder traversal for the BinarySearchTree class!
Instructions
Define a method .depth_first_traversal() below .get_node_by_value(). It should have self as the only parameter.
Fill the method body with a pass statement since it is not doing anything yet.
Inorder traversal means we will traverse the left child node followed by the root node and the right child node. Remove the pass statement you added in the previous step. Then, inside .depth_first_traversal():
- Check to see if the left child node exists
- If it does, call this method on the left child node
This traverses the left subtree.
Now we want to look at the root node. We can simply print out the depth and the value the root node contains.
After the if statement you just created, and on the same level of indentation as the if statement, add the following print statement which will print the root node’s depth and value:
The next step would be to traverse the right subtree. Add an if statement, right after the print() statement from the previous step, which will do the following:
- Checks to see if the right child node exists
- If it does, calls this method on the right child node
At the bottom of the BinarySearchTree.py file, call the .depth_first_traversal() method on the BinarySearchTree called tree, which has been provided, to print the inorder traversal of the tree.