search

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

To perform depth-first search (DFS) on a binary search tree (BST) in Python, you can use either a recursive approach or an iterative approach using a stack. Here's an example implementation of DFS using recursion:

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

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

    print(node.key, end=" ")

    depth_first_search_recursive(node.left)
    depth_first_search_recursive(node.right)

# Example usage:
# Constructing a binary search tree
root = Node(50)
root.left = Node(30)
root.right = Node(70)
root.left.left = Node(20)
root.left.right = Node(40)
root.right.left = Node(60)
root.right.right = Node(80)

# Performing depth-first search (recursive)
depth_first_search_recursive(root)

In this example, we use a Node class to represent the individual nodes of the binary search tree. The depth_first_search_recursive function performs DFS on the tree recursively, starting from the given node.

The algorithm begins by checking if the node is None. If it is, the function returns, as there are no more nodes to explore. Otherwise, it prints the key of the current node, then recursively calls itself to traverse the left and right subtrees in a depth-first manner.

The output of the example code would be:

50 30 20 40 70 60 80

This demonstrates how to perform depth-first search on a binary search tree using recursion. DFS explores the nodes in a depth-first manner, going as deep as possible along each branch before backtracking.

Related Questions You Might Be Interested