Skip to content

Implementing Depth-First Search in Python to Traverse a Binary Tree

Updated: at 05:45 AM

Depth-first search (DFS) is an important algorithm for traversing tree or graph data structures. In technical interviews, candidates are often asked to implement a DFS algorithm to traverse a binary tree. This algorithm explores branches of a tree or graph by going as deep as possible down each branch before backtracking and moving on to the next branch. In this comprehensive guide, we will cover the DFS algorithm in detail with Python example code and step-by-step explanations to traverse a binary tree data structure.

Table of Contents

Open Table of Contents

Overview of Depth-First Search Algorithm

The depth-first search algorithm starts at the root node of a tree or graph and explores as far as possible along each branch before backtracking. So it goes deep first before going wide.

The DFS algorithm follows these main steps:

  1. Start by placing any arbitrary node of the graph in a stack.

  2. Take the top item of the stack and add it to the visited list.

  3. Create a list of the adjacent nodes. Add the ones which aren’t in the visited list to the top of the stack.

  4. Keep repeating steps 2 and 3 until the stack is empty.

The above pseudocode shows the general logic of a recursive DFS implementation. The key points are:

Some key properties of depth-first search are:

Now let’s look at implementing DFS in Python specifically to traverse a binary tree data structure using code examples.

Binary Tree Data Structure in Python

A binary tree is a tree data structure where each node has at most two child nodes referred to as the left child and right child. In Python, we can create a Node class to represent each node in the tree:

class Node:
    def __init__(self, val=None):
        self.val = val
        self.left = None
        self.right = None

Here the Node class has a val to store node value and left and right attributes to represent left and right child nodes.

We can create a sample binary tree like:

root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')

This forms the sample binary tree structure:

     A
   /   \
  B     C
 /
D

Note that in the diagrams, nodes are shown as ovals with the node value inside. Edges point from parent to child nodes.

Now that we have our binary tree data structure in Python, next we can implement the depth-first search algorithm to traverse it.

Recursive Depth-First Search in Python

The recursive DFS approach is elegant and simple to implement in Python. We will define a traverse() function that takes a root node as input and recursively calls itself on the left and right child nodes:

def traverse(node):
    if node is None:
        return

    print(node.val)
    traverse(node.left)
    traverse(node.right)

Breaking this down:

To kick off the DFS, we need to initially call it on the root node:

root = Node('A')
# Set up tree structure ...

traverse(root)

The full program would be:

class Node:
    def __init__(self,val=None):
        self.val = val
        self.left = None
        self.right = None

def traverse(node):
    if node is None:
        return

    print(node.val)
    traverse(node.left)
    traverse(node.right)

root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')

traverse(root)

Output:

A
B
D
C

This recursively traverses the tree depth-first in pre-order (parent node visited before children).

The key advantage of the recursive approach is the code is very clean and simple. The call stack handles the node visits implicitly.

However, for very deep trees the recursive stack can get large, leading to stack overflow issues. So next we’ll look at an iterative version.

Iterative Depth-First Search in Python

We can implement the DFS algorithm iteratively using a stack. The logic will be:

This pushes nodes in the order we want to visit them.

Here is the Python code:

class Node:
  # Node class definition

def traverse(root):

  if root is None:
     return

  stack = []
  stack.append(root)

  while stack:

    node = stack.pop()
    print(node.val)

    if node.right:
      stack.append(node.right)

    if node.left:
      stack.append(node.left)

Key points:

This iteratively traverses the tree depth-first, but in reverse pre-order (children visited before parent) since we push children before visiting the parent node.

The iterative DFS avoids call stack limits for deep trees and can be faster for large graphs. But the code is more complex than the recursive DFS.

Comparing Depth-First Search Variants

There are a few common variants of the depth-first search algorithm:

The order determines when each node is processed relative to its children. Different orders are useful in various situations:

So in summary, recursive DFS provides a clean implementation, while iterative DFS avoids call stack limits. And several traversal orders are possible depending on the application’s requirements.

Some common applications of the DFS algorithm include:

DFS is thus a fundamental algorithm for working with tree and graph data structures with applications in compilers, AI, web crawlers, video games, and more.

Depth-First Search Python Implementation Summary

To summarize, here are the key points covered about implementing depth-first search in Python:

So in coding interviews, be sure to have a strong understanding of how to implement recursive and iterative depth-first search in Python. Both approaches have tradeoffs to consider for traversing binary trees and other data structures.