03. Binary Tree DFS Techniques

Binary Tree DFS Techniques

Depth-First Search (DFS) is a fundamental algorithm used to traverse or search tree or graph data structures. In the context of binary trees, DFS can be implemented in three primary ways: Inorder, Preorder, and Postorder traversal. Each of these traversals has a distinct order of visiting nodes.

1. Inorder Traversal (Left, Root, Right)

In Inorder traversal, the nodes are visited in the following order: left subtree, root, right subtree. This traversal is particularly useful for binary search trees (BSTs) because it visits the nodes in ascending order.

Algorithm:

1. Traverse the left subtree.
2. Visit the root node.
3. Traverse the right subtree.

Code:

def inorder_traversal(root):
    if root is not None:
        inorder_traversal(root.left)
        print(root.val, end=' ')
        inorder_traversal(root.right)

# Example usage:
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Constructing the binary tree
#       3
#      / \
#     9   20
#        /  \
#       15   7
tree = TreeNode(3)
tree.left = TreeNode(9)
tree.right = TreeNode(20, TreeNode(15), TreeNode(7))

inorder_traversal(tree)  # Output: 9 3 15 20 7

2. Preorder Traversal (Root, Left, Right)

In Preorder traversal, the nodes are visited in the following order: root, left subtree, right subtree. This traversal is useful for creating a copy of the tree or for prefix expression evaluation.

Algorithm:

1. Visit the root node.
2. Traverse the left subtree.
3. Traverse the right subtree.

Code:

def preorder_traversal(root):
    if root is not None:
        print(root.val, end=' ')
        preorder_traversal(root.left)
        preorder_traversal(root.right)

# Example usage:
preorder_traversal(tree)  # Output: 3 9 20 15 7

3. Postorder Traversal (Left, Right, Root)

In Postorder traversal, the nodes are visited in the following order: left subtree, right subtree, root. This traversal is useful for deleting nodes in a tree or for postfix expression evaluation.

Algorithm:

1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the root node.

Code:

def postorder_traversal(root):
    if root is not None:
        postorder_traversal(root.left)
        postorder_traversal(root.right)
        print(root.val, end=' ')

# Example usage:
postorder_traversal(tree)  # Output: 9 15 7 20 3

Iterative Approaches

While the above examples use recursion, DFS traversals can also be implemented iteratively using a stack.

Iterative Inorder Traversal

Code:

def iterative_inorder_traversal(root):
    stack, result = [], []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result

# Example usage:
print(iterative_inorder_traversal(tree))  # Output: [9, 3, 15, 20, 7]

Iterative Preorder Traversal

Code:

def iterative_preorder_traversal(root):
    if root is None:
        return []
    stack, result = [root], []
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

# Example usage:
print(iterative_preorder_traversal(tree))  # Output: [3, 9, 20, 15, 7]

Iterative Postorder Traversal

Code:

def iterative_postorder_traversal(root):
    if root is None:
        return []
    stack1, stack2, result = [root], [], []
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    while stack2:
        node = stack2.pop()
        result.append(node.val)
    return result

# Example usage:
print(iterative_postorder_traversal(tree))  # Output: [9, 15, 7, 20, 3]

Summary

• Inorder Traversal: Visits nodes in ascending order for BSTs (Left, Root, Right).
• Preorder Traversal: Useful for copying the tree and prefix expression (Root, Left, Right).
• Postorder Traversal: Useful for deleting nodes and postfix expression (Left, Right, Root).

Each traversal method has its unique applications and can be implemented both recursively and iteratively, depending on the problem requirements and constraints.