DSA 10# Depth-First Search of a Binary Tree
In this previous blog post we learned what a binary tree is, how it can be represented, and the different types of binary trees, in conclusion, we’ve said that a binary tree, unlike other data structures, can be browsed in two different ways breath-first search and depth-first search.
This post will be focused on depth-first search.
What’s depth-first search Tree traversal
The depth-first search is an algorithm that allows you to traverse an entire Tree. The logic is that you keep moving forward until you reach a leaf (a node that hasn’t left or right child) then backtrack according to the method you are using.
Depth-first search Tree traversal can be written in three ways: Pre Order, In Order, and Post Oder traversal. Each way can be written recursively and iteratively. The way you choose influences the result. Let’s me show you the difference:
Pre Order
The hint is on the name, Pre-order, when you are writing a pre-order traversal, you access the parent node then the left and the right child. If you traverse the tree above with the Pre Order method your result should be:
Let’s write the recursive and iterative implementation with javascript
Recursive
Explanation: since you know in which order you have to access the nodes, recursive methods are mostly straightforward. Here We have to access the parent node and then its children. so we push the current node’s value into the result array, and then check if it has a left or right child, if so we call the function by giving the child node and the result array.
Iterative
Explanation: the pre-order traversal is the straightforward method, if there isn’t any constraint you should prior to that method. Since we don’t need to check if a node has any children, we push the current node’s value to the result and then check if it has a child, if so they will be added to the stack. We push the right left before the right because we are using a stack and it follows the LIFO order.
In Order
For the in-order traversal, you have to access the left child before backtracking to the parent and then the right child. You have to keep moving forward while your current node has a left child. if you traverse the tree above with the In-Order method your result should be:
Let’s write the recursive and iterative implementation with javascript
Recursive
Explanation: since you know in which order you have to access the nodes, recursive methods are mostly straightforward. Here We have to access the left child before backtracking to the parent and then the right child, so we check if the current node has a left child if so, we call the function by giving the child, once it's done we push the node’s value into the result array and finally we check if a right child exists, if so we call the function by giving the right child.
Iterative
Explanation: For the in-order traversal, we have to push the left child, the parent, and then the right child. That means we have to keep moving forward since there is a left child. For the iterative implementation, the current loop will browse all the left children and then if there’s no left child, the current node’s value will be pushed into the result.
Post Order
For the post-order traversal, you have to access children before backtracking to the parent. You have to keep moving forward while your current node has children. if you traverse the tree above with the post-Order method your result should be:
Let’s write the recursive and iterative implementation with javascript
Recursive
Explanation: since you know in which order you have to access the nodes, recursive methods are mostly straightforward. Here We have to access children before the parent, so we check if the current node has a left or right child if so, we call the function by giving the child and then we push the value into the result array.
Iterative
Complexity analysis
Every approach that we have seen in this post has the same time and space complexity O(n) even the recursive approach because each recursive function use stack under the hood, to track the elements that you are traversing. Your choice will depend on the question you have to solve.
