How to perform depth-first search on a binary search tree in Python?

Question

Jayant Kumar · Accepted Answer

Table of Contents
Introduction
Depth-First Search (DFS) is a graph traversal algorithm that explores as far down a branch as possible before backtracking. When applied to a Binary Search Tree (BST), DFS can be implemented using three main traversal methods: in-order, pre-order, and post-order. Each method processes nodes in a different order, providing various ways to explore the tree.
1. Depth-First Search (DFS) Overview
DFS Traversal Methods

In-Order Traversal:

Visits nodes in the following order: left subtree, root node, right subtree.
For a BST, this results in nodes being visited in ascending order.

Pre-Order Traversal:

Visits nodes in the following order: root node, left subtree, right subtree.
Useful for creating a copy of the tree or performing actions on the root before its subtrees.

Post-Order Traversal:

Visits nodes in the following order: left subtree, right subtree, root node.
Ideal for tasks like deleting the tree where children are processed before the parent.

Use Cases

In-Order Traversal: Retrieve elements in sorted order.
Pre-Order Traversal: Useful for tree serialization or copying.
Post-Order Traversal: Useful for deleting nodes or processing the tree from bottom to top.

2. Python Implementation of DFS on a Binary Search Tree
Binary Search Tree Implementation
First, define the BST and implement the DFS traversal methods.
class BSTNode:
    def __init__(self, key):
        self.value = key
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

# Insert a node into the BST
    def insert(self, key):
        if self.root is None:
            self.root = BSTNode(key)
        else:
            self._insert_recursive(self.root, key)

def _insert_recursive(self, current, key):
        if key &#x3C; current.value:
            if current.left is None:
                current.left = BSTNode(key)
            else:
                self._insert_recursive(current.left, key)
        else:
            if current.right is None:
                current.right = BSTNode(key)
            else:
                self._insert_recursive(current.right, key)

# In-order traversal
    def in_order_traversal(self, node):
        if node:
            self.in_order_traversal(node.left)
            print(node.value, end=' ')
            self.in_order_traversal(node.right)

# Pre-order traversal
    def pre_order_traversal(self, node):
        if node:
            print(node.value, end=' ')
            self.pre_order_traversal(node.left)
            self.pre_order_traversal(node.right)

# Post-order traversal
    def post_order_traversal(self, node):
        if node:
            self.post_order_traversal(node.left)
            self.post_order_traversal(node.right)
            print(node.value, end=' ')

Example Usage
Here's how to use the BinarySearchTree class and perform the different DFS traversals.
# Create a Binary Search Tree and insert some nodes
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)

print("In-order Traversal:")
bst.in_order_traversal(bst.root)  # Output: 20 30 40 50 60 70 80

print("
Pre-order Traversal:")
bst.pre_order_traversal(bst.root)  # Output: 50 30 20 40 70 60 80

print("
Post-order Traversal:")
bst.post_order_traversal(bst.root)  # Output: 20 40 30 60 80 70 50

Conclusion
Performing Depth-First Search (DFS) on a Binary Search Tree (BST) involves using different traversal methods to explore nodes. In-order, pre-order, and post-order traversals each offer unique ways to process the tree's nodes. By implementing these traversals in Python, you can effectively navigate and manipulate BST structures for various applications, from sorting elements to managing hierarchical data.

How to perform depth-first search on a binary search tree in Python?

Similar Questions