Description

Binary tree traversal teaches us the ways we can traverse a binary tree. This concept is important to solve binary tree problems. There are 4 main types of tree traversal

1. In order traversal: Where we visit left sub-tree 1st, then parent node and in the end right sub-tree
2. Pre order traversal: Where we visit parent node 1st, then left sub-tree and in the end right sub-tree
3. Post order traversal: Where we visit left sub-tree 1st, then right sub-tree and in the end parent node
4. Level order traversal: Where we visit elements level by level, from left to right.

Usage

Following are few problems that utilizes these traversal approaches

1. Binary Tree Paths
2. Kth Smallest Element in a BST
3. Binary Tree Maximum Path Sum
4. Binary Tree Level Order Traversal II

In order traversal

In-order traversal method traverse a binary tree in this order

1. Recursively process left sub-tree nodes
2. Process current parent node
3. Recursively process right sub-tree nodes

The name signifies that tree is accessed in order, the way it is represented visually, Left -> Root -> Right.

This is the binary tree version of Depth First Search. It can be used to get sorted array from a Binary Search Tree.

Binary Search tree is a special type of Binary tree where all nodes in the left sub-tree are smaller than the parent node and all nodes in the right sub-tree are larger than the parent node.

This can provide optimized time complexity of $O(\log{N})$ to search, insert and delete operation in a balanced tree. Otherwise it degrades to $O(N)$.

Code

class Node:
    def __init__(self, val: int = None, left: Self = None, right: Self = None):
        self.val = val
        self.left = left
        self.right = right


def _in_order(node: Node, result: list) -> list[int]:
    if not node:
        return
    _in_order(node.left, result)
    result.append(node.val)
    _in_order(node.right, result)


def in_order(root: Node):
    result = list()
    _in_order(root, result)
    return result

Complexity

$\textbf{Time Complexity} = O(N) \text{, where N is number of nodes}$

• Each node is visited only once

$\textbf{Space Complexity} = O(N + H) \text{, where N is number of nodes and H is binary tree height}$

• Size of the result is of size N and there are a maximum of H stack frames due to recursion.

Pre order traversal

Pre-order traversal method traverse a binary tree in this order

1. Process current parent node
2. Recursively process left sub-tree nodes
3. Recursively process right sub-tree nodes

The name signifies that root of a tree is accessed before left and right children, i.e. Root -> Left -> Right.

Code

class Node:
    def __init__(self, val: int = None, left: Self = None, right: Self = None):
        self.val = val
        self.left = left
        self.right = right


def _pre_order(node: Node, result: list) -> list[int]:
    if not node:
        return

    result.append(node.val)
    _pre_order(node.left, result)
    _pre_order(node.right, result)


def pre_order(root: Node):
    result = list()
    _pre_order(root, result)
    return result

Complexity

$\textbf{Time Complexity} = O(N) \text{, where N is number of nodes}$

• Each node is visited only once

$\textbf{Space Complexity} = O(N + H) \text{, where N is number of nodes and H is binary tree height}$

• Size of the result is of size N and there are maximum a maximum of H stack frames due to recursion.

Post order traversal

Post-order traversal method traverse a binary tree in this order

1. Recursively process left sub-tree nodes
2. Recursively process right sub-tree nodes
3. Process current parent node

The name signifies that root of a tree is accessed after left and right children, i.e. Left -> Right -> Root.

Code

class Node:
    def __init__(self, val: int = None, left: Self = None, right: Self = None):
        self.val = val
        self.left = left
        self.right = right


def _post_order(node: Node, result: list) -> list[int]:
    if not node:
        return

    _post_order(node.left, result)
    _post_order(node.right, result)
    result.append(node.val)


def post_order(root: Node):
    result = list()
    _post_order(root, result)
    return result

Complexity

$\textbf{Time Complexity} = O(N) \text{, where N is number of nodes}$

• Each node is visited only once

$\textbf{Space Complexity} = O(N + H) \text{, where N is number of nodes and H is binary tree height}$

• Size of the result is of size N and there are maximum a maximum of H stack frames due to recursion.

Level order traversal

Level-order traversal method traverse a binary tree in order of depth, with 0 level being processed first and from left to right in same level.

Code

from collections import deque

class Node:
    def __init__(self, val: int = None, left: Self = None, right: Self = None):
        self.val = val
        self.left = left
        self.right = right


def level_order(root: Node):
    result = list()
    queue = deque([root])
    while len(queue):
        node = queue.popleft()
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

    return result

Complexity

$\textbf{Time Complexity} = O(N) \text{, where N is number of nodes}$

• Each node is visited only once

$\textbf{Space Complexity} = O(N + W) \text{, where N is number of nodes and W is max width of the tree }$

• Size of the result is of size N and queue can have almost W elements at a times.