Binary Tree Traversal: DFS

Photo by niko photos on Unsplash

Hello everyone! Today we will be discussing tree traversal. There are two fundamental algorithms: DFS (depth-first search) and BFS (breadth-first search). In this article, we will be focusing on DFS.

DFS (Depth-first-search)

In DFS, also known as depth-first search, we prioritize depth by traversing the tree as far down as possible in one direction (continuing until we reach a leaf node) before backtracking and traversing the other direction. The three types of DFS algorithms are inorder (left-root-right), preorder (root-left-right), and postorder (left-right-root).

DFS (Depth-first-search) using preorder traversal on BST. It follows the pattern of root-left-right.

DFS Implementation

We can implement DFS iteratively by using a stack. Here is an example solution to find the maximum depth of a binary tree in Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        stack = [(root, 1)]
        ans = 0
        
        while stack:
            node, depth = stack.pop()
            ans = max(ans, depth)
            if node.left:
                stack.append((node.left, depth + 1))
            if node.right:
                stack.append((node.right, depth + 1))
        
        return ans

The intuition behind finding the maximum depth in the fastest way possible is calculating the maximum number of steps it takes to reach a leaf node from the root, which can be done by implementing a depth-first search. We start off by initializing the stack as [(root, 1)], which indicates the first level of the tree. Then, we use a while loop to process the rest of the nodes in the tree. The stack.pop() function removes the last node added to the stack and gives the current node and its depth. We will process this current node by checking the existence of its children. The depth of the children from the current node is depth + 1. If the current node has children, the current node’s children will then be added to the stack to be processed in the next iteration.

Let’s look an example.

                                    3
                                   / \
                                  9   20
                                      /  \
                                    15    7

We start at the root, which is 3 and has a depth of 1. We initialize the root and its depth in our stack. When we run this through our while loop, we start off by removing this node from our stack and initialize our current node and depth. Then, we store its depth in ans = max(ans, depth). Does our current node have children? Yes, it has children 9 and 20, so both left and right nodes will be added to our stack along with their depth (calculated as depth + 1). By the end of our first iteration, this is how our stack looks like:

stack = [(9, 2), (20, 2)]  
ans = 1 #we are storing the depth from the previous node

Stack follows LIFO (last-in-first-out), so the next node to be processed is 20. In our stack, this is processed as (20, 2). We update our ans to the current depth using the max function, which is now 2. Does 20 have left and right children? Yes, it has children 15 and 7, so both nodes will be added to the stack. Now, this is our current stack, with our updated ans:

stack = [(9, 2), (15, 3), (7, 3)]  
ans = 2

Now we remove node 7 from our stack, then update ans to the level of our current node, which is 3. Does 7 have a left child? No, so nothing will be added to the stack. Does it have a right child? Also no, so again nothing will be added to our stack. Since 7 doesn’t have either left or right children, this signifies that we have encountered a leaf node.

stack = [(9, 2), (15, 3)]  
ans = 3

Since no new nodes were added, we visit node 15 which had been previously added to our stack. This is also known as backtracking. We remove 15 from the stack, and check whether it has left or right children. Our max depth is still 3 so ans will remain unchanged.

stack = [(9, 2)]  
ans = 3

Finally, we come back to node 9, remove it from our stack, and repeat the same process. The depth of 9 is 2 and the max depth is 3, so ans still remains unchanged. It doesn’t have any children, so nothing will be added to the stack. Now, our stack is empty, which means that we can come out of our loop. Once we are out of the while loop, we return the value of ans, which is 3.

Time and Space Complexity

Since we visit each node and check whether it has left or right children exactly once, the time complexity is O(n). Since the height of a balanced binary tree is log(n), the space complexity is O(log(n)).

The purpose of this article is to reinforce my understanding of the iterative implementation of DFS. I hope this was helpful for you too!