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 25
We 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, 11
We 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, 14
We 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, 19
We 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, 25
The entire inorder traversal becomes:
8, 10, 11, 12, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 25
Notice 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
:
print(f'Depth={self.depth}, Value={self.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.