Understanding Binary Tree Traversal in Python

Understanding Binary Tree Traversal in Python:



There are two different types of binary tree traversal, Depth First Traversal (DFT) and Breadth First Traversal (BFT).

Firstly, Depth First Traversal is a way of moving forward through the Nodes while visiting each one in a certain order, moving from node to node left and right until we find a dead end. Every single node is visited, and the order changes based upon the type of DFT. There are 3 types of DFT: inorder, preorder, and postorder traversal. These different types of DFT can be implemented recursively or iteratively. We might make the choice to implement recursively if we’re using a stack.

Inorder traversal ~ left, Node, right. As the name suggests, this would potentially print in order.

Preorder traversal ~ Node, left, right.

Postorder traversal ~ left, right, Node.

Here is what an inorder traversal could look like in Python:

class TreeNode:
def init(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def helper(root, res):
if root is None:
helper(root.left, res) <—– The left
res,append(root.val) <—– The Node!!!
helper(root.right, res) <—– The right
def inorder_traversal(root):
result = []
helper(root, result)

As we can clearly see from the above example written in Python (that I grabbed from one of my school videos for educational purposes) the patterns… (like ‘left, right, Node’) no matter what the order is, inorder, postorder, or preorder, it can be CLEARLY seen in the code.

The only part that we need to pay attention to are the lines with the arrow. Let’s call them left, right, and NODE. The only part of this code that needs to change is the placement of the append for us to manipulate this code to write all three different DFT’s.

Remember left, Node, right was the order for inorder traversal. So if we wanted to change this code to make it a postorder traversal, we’d just move the “Node” line of code down one to where “helper(root.right, res)” is and basically move the “right” line of code up one, we’re switching the Node line with the right line to make the order ‘left, right, Node’.

I didn’t want to breakdown the entirety of the code. I just wanted to touch on the fact that all three DFT’s can be written almost the exact same aside from three small lines of code.

Now on to the BFT’s. 
In a Breadth First Traversal (sometimes called a level order traversal), we would need to visit all of the Nodes on the same level before we move on to the next level. We can’t do this with a recursive function. We need to utilize a queue to do this. The data structure for a queue is first in first out.


from Tumblr https://generouspiratequeen.tumblr.com/post/632606915858481152

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s