Module 6.1 ⏱ 45 min read ⚡ Trees & Graph Traversals

Binary Trees & Traversals

Master fundamental tree terminology, Depth-First Search (DFS) orderings, and Breadth-First Search (BFS) level-order traversal.

1. Tree Terminology & Binary Tree Properties

A binary tree is a hierarchical data structure consisting of nodes, where each node has at most two children referred to as the left child and the right child. Key terminology includes:

Root: The topmost node of a tree from which all other nodes branch out.

Leaf: A node that has no children (both left and right pointers are null).

Height & Depth: The depth of a node is its distance from the root, while the height of a tree is the maximum depth of any node within it.

2. Depth-First Search (DFS) & Breadth-First Search (BFS)

Traversing tree structures allows us to inspect or process every node systematically:

DFS Orderings: Depth-first search explores branches deeply before backtracking. Depending on when the root is visited relative to its subtrees, DFS is classified into **Pre-order** (Root, Left, Right), **In-order** (Left, Root, Right), and **Post-order** (Left, Right, Root).

BFS (Level Order Traversal): Breadth-first search processes nodes level by level from top to bottom, typically implemented using a **Queue** data structure.

// C++ Solution: Binary Tree Level Order Traversal (BFS)
#include <vector>
#include <queue>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    std::vector<std::vector<int>> levelOrder(TreeNode* root) {
        std::vector<std::vector<int>> result;
        if (!root) return result;
        std::queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();
            std::vector<int> level;
            for (int i = 0; i < size; ++i) {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            result.push_back(level);
        }
        return result;
    }
};
            

# Python Solution: Binary Tree Level Order Traversal (BFS)
from collections import deque

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

class Solution:
    def levelOrder(self, root: TreeNode) -> list[list[int]]:
        result = []
        if not root:
            return result
        q = deque([root])
        while q:
            size = len(q)
            level = []
            for _ in range(size):
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            result.append(level)
        return result
            

// Java Solution: Binary Tree Level Order Traversal (BFS)
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                level.add(node.val);
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
            result.add(level);
        }
        return result;
    }
}
            

3. Homework & Quiz Overview

To lock in your mastery, complete the implementation exercises for finding the Maximum Depth of a Binary Tree and implementing Level Order Traversal.

Quick Check: Test Your Intuition

Which DFS traversal strategy visits the left subtree first, then the root node, and finally the right subtree?