Depth First Search Tree in Python

Depth-first search (DFS) is a method of visiting all the nodes of a tree or a graph in a depth-first manner, i.e., visiting a node and all its descendants before moving on to the next sibling. There are three main variations of DFS: pre-order, in-order, and post-order.

Here is a basic implementation of pre-order depth-first search on a tree in Python 3.10:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = Noneclass BinaryTree:
    def __init__(self):
        self.root = Nonedef pre_order_dfs(self, node, result):
        if node is None:
            return

        result.append(node.value)
        self.pre_order_dfs(node.left, result)
        self.pre_order_dfs(node.right, result)

    def pre_order_traversal(self):
        result = []
        self.pre_order_dfs(self.root, result)
        return result

The above implementation of pre-order depth-first search on a binary tree uses recursion to traverse the tree in a depth-first manner. The pre_order_dfs method visits a node and all its descendants before moving on to the next sibling and appends the nodes' values to the result list. The pre_order_traversal method calls the pre_order_dfs method and returns the list of the nodes' values in the order they were visited.

Time complexity of depth-first search in a binary tree:

• The time complexity of depth-first search is O(n), where n is the number of nodes in the tree. This is because each node in the tree is visited exactly once.

Space complexity of depth-first search in a binary tree:

• The space complexity of depth-first search is O(h), where h is the height of the tree. This is because in the worst case, the recursion will use h function calls, each of which takes O(1) space.