I decided the best way for me to understand basic data structures and algorithms is for me to write a little bit about them during my learning process. This is in no way an in-depth description of how these complex computer science concepts work. I'll be explaining things as though I'm talking to a 3-year-old. This is just a place for me to share simple notes and attempt to explain what I am learning. As I learn more, I'll publish more or update my postings. Like a diary but I'm gonna be talking about code and tech stuff and not my obsession with Shonen anime, ramen, and German culture.
Today I am going to explain what I learned about binary tree traversal. Please feel free to add anything in the comment section below, I'm always open to new ideas and perspectives as well as constructive criticism. Now on to the explanation.
From my understanding, 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:
return
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)
return(result)
As we can clearly see from the above example written in Python (that I grabbed from a video 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. And I'll talk about queues in another post. :)
**(wink wink)
Credits:
Author: 👩🏽💻 Kodebae
Buy me a ☕️: (https://www.buymeacoffee.com/karmendurbin)
Website: (https://karmen-durbin-swe.netlify.app/)
X: (https://twitter.com/karmen_durbin)
Top comments (0)