How to Implement DFS Traversal with Recursion in Python

Submitted by razormist on Friday, March 13, 2026 - 23:10.

In this tutorial, we will learn how to program “How to Implement DFS Traversal with Recursion in Python.” The main objective is to understand how to implement DFS traversal using recursion. This tutorial will guide you step by step through the process of implementing DFS traversal. By the end of this tutorial, you will have a solid understanding of how DFS traversal works in Python, helping you strengthen your problem-solving abilities and improve your overall coding skills in data structure implementation.

This topic is straightforward and easy to understand. By simply following the instructions provided, you will be able to complete it with ease. The program will guide you step by step through the process of implementing DFS Traversal with Recursion. So, let’s dive into the coding process and start implementing the solution to gain a deeper understanding of graph traversal algorithms in Python.

Getting Started:

First you will have to download & install the Python IDLE's, here's the link for the Integrated Development And Learning Environment for Python https://www.python.org/downloads/.

Creating Main Function

This is the main function of the application. The following code will display a simple GUI in terminal console that will display program. To do this, simply copy and paste these blocks of code into the IDLE text editor.

class BinaryTree:
    def __init__(self, key=None):
        self.key = key
        self.left = None
        self.right = None
 
    def set_root(self, key):
        self.key = key
 
    def insert_left(self, new_node):
        self.left = new_node
 
    def insert_right(self, new_node):
        self.right = new_node
 
    def search(self, key):
        if self.key == key:
            return self
 
        if self.left is not None:
            temp = self.left.search(key)
            if temp is not None:
                return temp
 
        if self.right is not None:
            temp = self.right.search(key)
            return temp
 
        return None
 
    def depth_first(self):
        print("entering {}...".format(self.key))
 
        if self.left is not None:
            self.left.depth_first()
 
        print("at {}...".format(self.key))
 
        if self.right is not None:
            self.right.depth_first()
 
        print("leaving {}...".format(self.key))
 
 
# MAIN PROGRAM
while True:
 
    print("\n================= Implement DFS Traversal with Recursion =================\n")
 
    btree = None
 
    print("Menu (this assumes no duplicate keys)")
    print("insert <data> at root")
    print("insert <data> left of <data>")
    print("insert <data> right of <data>")
    print("dfs")
    print("quit")
 
    while True:
 
        do = input("\nWhat would you like to do? ").split()
 
        if len(do) == 0:
            continue
 
        operation = do[0].lower()
 
        if operation == "insert":
 
            data = int(do[1])
            new_node = BinaryTree(data)
 
            suboperation = do[2].lower()
 
            if suboperation == "at":
                btree = new_node
 
            else:
                key = int(do[4])
 
                ref_node = None
                if btree is not None:
                    ref_node = btree.search(key)
 
                if ref_node is None:
                    print("No such key.")
                    continue
 
                if suboperation == "left":
                    ref_node.insert_left(new_node)
 
                elif suboperation == "right":
                    ref_node.insert_right(new_node)
 
        elif operation == "dfs":
 
            print("\nDepth-first search traversal:")
 
            if btree is not None:
                btree.depth_first()
            else:
                print("Tree is empty.")
 
            print()
 
        elif operation == "quit":
            break
 
        else:
            print("Invalid command.")
 
    # Try Again Option
    opt = input("\nDo you want to try again? (yes/no): ").strip().lower()
 
    if opt == "no":
        print("Exiting program...")
        break
    elif opt != "yes":
        print("Invalid choice. Exiting program...")
        break

This program demonstrates how to implement a Depth-First Search (DFS) traversal on a binary tree using recursion. It defines a `BinaryTree` class where each node has a key and pointers to left and right children. Users can build a binary tree interactively through a menu by inserting a node at the root or attaching nodes as the left or right child of an existing node. The `depth_first` method performs a DFS traversal, printing messages as it "enters" a node, visits it, and "leaves" it, giving a clear visualization of the recursive traversal order. The program also allows searching for nodes by key to attach new nodes correctly and provides an option to quit or repeat the process. It ensures the tree is traversed recursively and outputs the DFS path step by step.

Output:

There you have it we successfully created How to Implement DFS Traversal with Recursion in Python. I hope that this simple tutorial help you to what you are looking for. For more updates and tutorials just kindly visit this site. Enjoy Coding!

More Tutorials for Python Language

Python Tutorials