Python Program for Depth First Binary Tree Search using Recursion

In the following example of a Python program that performs a depth-first search on a binary tree using recursion :

Program :

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

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

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert(value, self.root)

    def _insert(self, value, node):
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert(value, node.left)
        else:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert(value, node.right)

    def dfs_inorder(self):
        if self.root is None:
            return []
        return self._dfs_inorder(self.root)

    def _dfs_inorder(self, node):
        result = []
        if node.left is not None:
            result += self._dfs_inorder(node.left)
        result.append(node.value)
        if node.right is not None:
            result += self._dfs_inorder(node.right)
        return result

# Example usage
tree = BinaryTree()
tree.insert(5)
tree.insert(3)
tree.insert(7)
tree.insert(1)
tree.insert(4)
tree.insert(6)
tree.insert(8)

inorder_traversal = tree.dfs_inorder()
print("Inorder Traversal:", inorder_traversal)

Output :

Inorder Traversal: [1, 3, 4, 5, 6, 7, 8]

In this example, the `Node` class and `BinaryTree` class are the same as in the previous examples. The new method `dfs_inorder()` performs a depth-first search on the binary search tree and returns a list containing the values of the nodes visited in inorder traversal.

It calls the helper method `_dfs_inorder(node)` to perform the recursive traversal. At each node, the method first traverses the left subtree, then adds the current node's value to the result list, and finally traverses the right subtree.

The example usage at the bottom of the program constructs a binary search tree with some example values, and then calls `dfs_inorder()` to perform a depth-first search on the tree in inorder traversal. The resulting list is printed to the console.