Depth First Search of a Binary Tree

Introduction

In a DFS, we prioritize depth by traversing as far down the tree as possible in one direction (until reaching a leaf node) before considering the other direction.

Base Template of DFS for a Binary Tree:

def dfs(node):
    if node == None:
        return
 
    dfs(node.left)
    dfs(node.right)
    return

The most important thing to understand when it comes to solving binary tree problems is that each function call solves and returns the answer to the original problem as if the subtree rooted at the current node was the input.

So the important thing to start with when approaching these problems is the smallest possible implementation of a binary tree.

Traversal Patterns

Preorder Traversals

In preorder traversal, logic is done on the current node before moving to the children.

def preorder_dfs(node):
    if not node:
        return
 
    print(node.val)
    preorder_dfs(node.left)
    preorder_dfs(node.right)
    return

In-Order Traversal

For inorder traversal, we first recursively call the left child, then perform logic (print in this case) on the current node, and then recursively call the right child. This means no logic will be done until we reach a node without a left child since calling on the left child takes priority over performing logic.

def inorder_dfs(node):
    if not node:
        return
 
    inorder_dfs(node.left)
    print(node.val)
    inorder_dfs(node.right)
    return

Notice that for any given node, its value is not printed until all values in the left subtree are printed, and values in its right subtree are not printed until after that.

Post-Order Traversal

In postorder traversal, we recursively call on the children first and then perform logic on the current node. This means no logic will be done until we reach a leaf node since calling on the children takes priority over performing logic. In a postorder traversal, the root is the last node where logic is done.

def postorder_dfs(node):
    if not node:
        return
 
    postorder_dfs(node.left)
    postorder_dfs(node.right)
    print(node.val)
    return

Notice that for any given node, no values in its right subtree are printed until all values in its left subtree are printed, and its own value is not printed until after that.

Quick Mental Trick

• Pre → before children
• In → in the middle of children
• Post → after children

---

Linked Map of Contexts