Buổi 08 — Tree: DFS & BFS

Navigation

← 07-Hash-Table | → 09-Graph-DFS-BFS Giai đoạn: Big Tech Foundation | Độ khó: ⭐⭐⭐

1. Analogy & Context

Tree = Sơ đồ tổ chức công ty (Company Org Chart)

Hãy tưởng tượng một công ty lớn:

CEO nằm ở root — đỉnh của cây
Managers / Directors là các internal nodes — có con trực tiếp
Employees ở tầng thấp nhất là leaf nodes — không có con

DFS (Depth-First Search) = Nhân viên tham vọng Người này muốn khám phá toàn bộ một phòng ban từ trên xuống trước khi chuyển sang phòng ban khác. Họ đi sâu vào một nhánh đến tận cùng rồi mới backtrack lại.

BFS (Breadth-First Search) = HR làm khảo sát HR đi từng tầng một — gặp tất cả mọi người ở tầng 1 trước, rồi mới xuống tầng 2, tầng 3. Mỗi tầng được xử lý hoàn toàn trước khi đi tiếp.

Khi nào dùng DFS vs BFS?

DFS: Tìm đường, path sum, kiểm tra cấu trúc cây (validate BST, symmetric)

BFS: Level order traversal, tìm độ sâu tối thiểu, khoảng cách ngắn nhất trong unweighted graph

Context thực tế:

File system trên máy tính (folders & files) là một tree
HTML DOM là một tree
Compiler parse expression thành AST (Abstract Syntax Tree)
Git commit history là một directed tree

2. The FAANG Standard

Binary Tree = Chủ đề phổ biến nhất trong FAANG

Binary tree problems chiếm hơn 25% tổng số câu hỏi phỏng vấn tại Google, Meta, Amazon, Apple, Netflix.

Những gì FAANG interviewer mong đợi:

Kỹ năng	Mức độ quan trọng	Ghi chú
Inorder / Preorder / Postorder	⭐⭐⭐⭐⭐	Phải biết cả recursive lẫn iterative
Level Order (BFS)	⭐⭐⭐⭐⭐	Queue-based, hay bị hỏi
Lowest Common Ancestor (LCA)	⭐⭐⭐⭐⭐	Classic Medium/Hard
Validate BST	⭐⭐⭐⭐	Dễ sai nếu không dùng bounds
Path Sum problems	⭐⭐⭐⭐	Có thể có số âm — cẩn thận
Serialize / Deserialize	⭐⭐⭐	L6 / Staff level
Tree construction from traversals	⭐⭐⭐	Inorder + Preorder → Tree

L4 expectation (SWE II / IC4): Giải được DFS/BFS, validate BST, LCA trong 20 phút.

L5 expectation (Senior / IC5): Giải được Max Path Sum, Serialize/Deserialize, nhận biết pattern nhanh và discuss trade-offs.

3. Visual Thinking (Mermaid)

3.1 Binary Tree với các level được đánh nhãn

graph TD
    A["3 (root, level 0)"]
    B["9 (level 1)"]
    C["20 (level 1)"]
    D["null (level 2)"]
    E["null (level 2)"]
    F["15 (level 2)"]
    G["7 (level 2)"]

    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G

    style A fill:#ff9f43,color:#000
    style B fill:#54a0ff,color:#000
    style C fill:#54a0ff,color:#000
    style F fill:#5f27cd,color:#fff
    style G fill:#5f27cd,color:#fff

3.2 DFS Traversal Orders — cùng một cây, thứ tự khác nhau

flowchart LR
    subgraph Preorder["Preorder: Root → Left → Right"]
        direction TB
        P1["① Visit 3"] --> P2["② Visit 9"] --> P3["③ Visit 20"] --> P4["④ Visit 15"] --> P5["⑤ Visit 7"]
    end

    subgraph Inorder["Inorder: Left → Root → Right (BST → sorted!)"]
        direction TB
        I1["① Visit 9"] --> I2["② Visit 3"] --> I3["③ Visit 15"] --> I4["④ Visit 20"] --> I5["⑤ Visit 7"]
    end

    subgraph Postorder["Postorder: Left → Right → Root"]
        direction TB
        O1["① Visit 9"] --> O2["② Visit 15"] --> O3["③ Visit 7"] --> O4["④ Visit 20"] --> O5["⑤ Visit 3"]
    end

3.3 BFS Level-by-Level với Queue

sequenceDiagram
    participant Q as Queue
    participant R as Result

    Note over Q: Init: [3]
    Q->>R: Dequeue 3 → result[[3]]
    Note over Q: Enqueue children: [9, 20]
    Q->>R: Dequeue 9, 20 → result[[3],[9,20]]
    Note over Q: Enqueue children: [15, 7]
    Q->>R: Dequeue 15, 7 → result[[3],[9,20],[15,7]]
    Note over Q: Queue empty → Done

4. TypeScript Template

4.1 TreeNode Class Definition

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
 
  constructor(val: number = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

4.2 DFS — Inorder, Preorder, Postorder

// ===== RECURSIVE (Clean, Preferred for interviews) =====
 
function inorderRecursive(root: TreeNode | null): number[] {
  const result: number[] = [];
 
  function dfs(node: TreeNode | null): void {
    if (!node) return;
    dfs(node.left);       // Left
    result.push(node.val); // Root
    dfs(node.right);      // Right
  }
 
  dfs(root);
  return result;
}
 
function preorderRecursive(root: TreeNode | null): number[] {
  const result: number[] = [];
 
  function dfs(node: TreeNode | null): void {
    if (!node) return;
    result.push(node.val); // Root first
    dfs(node.left);
    dfs(node.right);
  }
 
  dfs(root);
  return result;
}
 
function postorderRecursive(root: TreeNode | null): number[] {
  const result: number[] = [];
 
  function dfs(node: TreeNode | null): void {
    if (!node) return;
    dfs(node.left);
    dfs(node.right);
    result.push(node.val); // Root last
  }
 
  dfs(root);
  return result;
}
 
// ===== ITERATIVE INORDER — Hay bị hỏi trong interview! =====
// Pattern: dùng explicit stack để simulate call stack
 
function inorderIterative(root: TreeNode | null): number[] {
  const result: number[] = [];
  const stack: TreeNode[] = [];
  let curr: TreeNode | null = root;
 
  while (curr !== null || stack.length > 0) {
    // Go as far left as possible
    while (curr !== null) {
      stack.push(curr);
      curr = curr.left;
    }
    // Process node
    curr = stack.pop()!;
    result.push(curr.val);
    // Move to right subtree
    curr = curr.right;
  }
 
  return result;
}

Iterative Inorder Pattern

Đây là một trong những câu hỏi hay bị hỏi nhất. Nhớ pattern: “go left as far as possible → pop → go right”. Hiểu tại sao cần check curr !== null || stack.length > 0.

4.3 BFS — Level Order Traversal

// Pattern: index pointer thay cho queue.shift() để giữ O(1) dequeue.
// Xem 03-Stack-and-Queue § Pitfall 2 vì sao queue.shift() là O(N).
function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
 
  const result: number[][] = [];
  const queue: TreeNode[] = [root];
  let head = 0; // Index pointer — không dùng .shift()!
 
  while (head < queue.length) {
    const levelSize = queue.length - head; // Snapshot — critical!
    const currentLevel: number[] = [];
 
    for (let i = 0; i < levelSize; i++) {
      const node = queue[head++];
      currentLevel.push(node.val);
 
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
 
    result.push(currentLevel);
  }
 
  return result;
}

Key insight BFS

const levelSize = queue.length phải được snapshot trước vòng lặp. Nếu check queue.length trực tiếp trong loop condition, nó sẽ thay đổi khi ta enqueue children và làm hỏng level separation.

4.4 maxDepth — Recursive $O (N)$

function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;
 
  const leftDepth = maxDepth(root.left);
  const rightDepth = maxDepth(root.right);
 
  return 1 + Math.max(leftDepth, rightDepth);
}
 
// Iterative BFS version — đếm số levels
function maxDepthBFS(root: TreeNode | null): number {
  if (!root) return 0;
 
  let depth = 0;
  const queue: TreeNode[] = [root];
  let head = 0;
 
  while (head < queue.length) {
    const levelSize = queue.length - head;
    depth++;
 
    for (let i = 0; i < levelSize; i++) {
      const node = queue[head++];
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
 
  return depth;
}

4.5 isValidBST — Min/Max Bounds Approach

// WRONG approach: chỉ check node.left.val < node.val
// VÍ DỤ LỖI:
//     5
//    / \
//   1   4
//      / \
//     3   6
// Node 4 < 5 nhưng subtree của 4 vi phạm BST (4 < 5 nhưng thuộc right subtree)
 
// CORRECT: truyền min/max bounds xuống
function isValidBST(root: TreeNode | null): boolean {
  function validate(node: TreeNode | null, min: number, max: number): boolean {
    if (!node) return true;
 
    if (node.val <= min || node.val >= max) return false;
 
    return (
      validate(node.left, min, node.val) &&   // left child must be < current
      validate(node.right, node.val, max)      // right child must be > current
    );
  }
 
  return validate(root, -Infinity, Infinity);
}

BST Validation — Lỗi phổ biến nhất

Không thể chỉ check immediate children! Một node ở right subtree phải lớn hơn tất cả ancestors bên trái của nó. Luôn dùng min/max bounds truyền xuống từ trên.

4.6 Lowest Common Ancestor (LCA)

// LCA trong BST — có thể dùng BST property
function lcaBST(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  if (!root) return null;
 
  if (p.val < root.val && q.val < root.val) {
    return lcaBST(root.left, p, q);   // Cả hai ở left
  }
  if (p.val > root.val && q.val > root.val) {
    return lcaBST(root.right, p, q);  // Cả hai ở right
  }
 
  // Split point — current node là LCA
  return root;
}
 
// LCA trong Binary Tree thông thường (không phải BST)
function lcaBinaryTree(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  if (!root) return null;
  if (root === p || root === q) return root; // Found one of the targets
 
  const left = lcaBinaryTree(root.left, p, q);
  const right = lcaBinaryTree(root.right, p, q);
 
  // Nếu cả left và right đều trả về non-null → current node là LCA
  if (left && right) return root;
 
  // Chỉ một bên tìm thấy → trả về bên đó
  return left ?? right;
}

4.7 Path Sum — Root-to-Leaf

// Kiểm tra có tồn tại path root → leaf có sum = targetSum không
function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
  if (!root) return false;
 
  // Leaf node: kiểm tra remaining sum
  if (!root.left && !root.right) {
    return root.val === targetSum;
  }
 
  return (
    hasPathSum(root.left, targetSum - root.val) ||
    hasPathSum(root.right, targetSum - root.val)
  );
}
 
// Trả về tất cả các paths có sum = targetSum
function pathSumAll(root: TreeNode | null, targetSum: number): number[][] {
  const result: number[][] = [];
 
  function dfs(node: TreeNode | null, remaining: number, path: number[]): void {
    if (!node) return;
 
    path.push(node.val);
 
    if (!node.left && !node.right && remaining === node.val) {
      result.push([...path]); // Copy vì path sẽ bị modify sau
    }
 
    dfs(node.left, remaining - node.val, path);
    dfs(node.right, remaining - node.val, path);
 
    path.pop(); // Backtrack
  }
 
  dfs(root, targetSum, []);
  return result;
}

5. Complexity Deep-dive

Time & Space Complexity

Operation	Time	Space	Ghi chú
DFS (any traversal)	$O (N)$	$O (H)$	H = height của cây
BFS (level order)	$O (N)$	$O (W)$	W = max width của cây
Insert vào BST	$O (H)$	$O (1)$ iterative	$O (H)$ recursive
Search trong BST	$O (H)$	$O (1)$ iterative
maxDepth	$O (N)$	$O (H)$	Visit all nodes
isValidBST	$O (N)$	$O (H)$	Visit all nodes
LCA	$O (N)$	$O (H)$	Worst case full traversal

Balanced vs Skewed Trees

$H_{ba l an ce d} = O (lo g N)$ $H_{s k e w e d} = O (N)$

Space complexity quan trọng

Balanced tree: DFS space $O (lo g N)$ , BFS space $O (N /2) = O (N)$ (last level có N/2 nodes)

Skewed tree (worst case linked list): DFS space $O (N)$ , BFS space $O (1)$ (mỗi level chỉ có 1 node)

BFS tốn nhiều memory hơn DFS đối với cây rộng và cân bằng!

Tại sao BFS tốn nhiều space?

Tại level cuối cùng của một perfect binary tree với N nodes, số lượng leaf nodes là $\frac{N + 1}{2} \approx \frac{N}{2}$ .

Queue của BFS phải chứa toàn bộ level này → $O (N)$ space.

6. Edge Cases & Pitfalls

Null Root — Luôn check đầu tiên

// WRONG: Crash nếu root là null
function maxDepth(root: TreeNode): number {
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
 
// CORRECT: Base case cho null
function maxDepth(root: TreeNode | null): number {
  if (!root) return 0; // ← Always handle this!
  ...
}

BST Property — Không chỉ check immediate children

Đã giải thích ở phần 4.5. Luôn dùng min/max bounds, không chỉ compare với parent.

Integer Overflow trong BST validation

// WRONG: số Integer có thể bằng Number.MAX_VALUE
validate(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER)
 
// CORRECT: dùng -Infinity và Infinity
validate(root, -Infinity, Infinity)

Iterative Inorder — Lỗi thường gặp khi implement

Condition của while loop phải là curr !== null || stack.length > 0. Chỉ check một trong hai sẽ bỏ sót nodes.

Path Sum với số âm

Không thể prune (dừng sớm) khi thấy sum vượt quá target, vì có thể có negative values phía sau. Phải explore toàn bộ path đến leaf.

Confusing Tree Types

Binary Tree: mỗi node có tối đa 2 con — không có ordering constraint

BST (Binary Search Tree): left < root < right, áp dụng cho toàn bộ subtree

Complete Binary Tree: tất cả levels đầy trừ level cuối, được fill từ trái sang

Perfect Binary Tree: tất cả internal nodes có đúng 2 con, tất cả leaves cùng level

7. Pattern Recognition

Khi thấy những từ khóa này → nghĩ đến Tree DFS/BFS:

Từ khóa trong đề	Pattern nên dùng
”height / depth of tree”	DFS recursive, base case = null → 0
”level order” / “by level”	BFS với queue, snapshot levelSize
”validate BST”	DFS với min/max bounds
”path sum” / “root to leaf”	DFS với backtracking, path array
”lowest common ancestor”	DFS bottom-up, return node when found
”serialize / deserialize”	BFS for level-order serialization
”symmetric tree”	DFS compare left.left vs right.right
”diameter of tree”	DFS, diameter = max(leftH + rightH)
“invert / mirror tree”	DFS preorder, swap left and right
”construct from traversals”	Divide & conquer, preorder root splits inorder

Nhận diện nhanh

Cần thứ tự theo level → BFS

Cần explore toàn bộ path → DFS + recursion

Có BST property → khai thác để bỏ qua half subtree

Cần return giá trị từ subtrees → DFS postorder (left và right trước, rồi combine)

8. Top LeetCode Problems

Danh sách theo thứ tự học

#	Problem	Difficulty	Kỹ năng cần	Ghi chú
LC-104 #104	Maximum Depth of Binary Tree	Easy	DFS recursive	Warm-up
LC-226 #226	Invert Binary Tree	Easy	DFS preorder	Classic
LC-102 #102	Binary Tree Level Order Traversal	Medium	BFS + levelSize trick	Must-know
LC-98 #98	Validate Binary Search Tree	Medium	DFS + bounds	Tricky nếu không dùng bounds
LC-236 #236	LCA of Binary Tree	Medium	DFS bottom-up	L5 classic
LC-105 #105	Construct BT from Preorder + Inorder	Medium	Divide & conquer	Khó hơn vẻ ngoài
LC-543 #543	Diameter of Binary Tree	Medium	DFS, global max	Pattern mới
LC-297 #297	Serialize and Deserialize Binary Tree	Hard	BFS or DFS	L6 question
LC-124 #124	Binary Tree Maximum Path Sum	Hard	DFS postorder	Tricky path definition

Complete Solution: #124 Binary Tree Maximum Path Sum

Problem Statement

Cho một binary tree, tìm maximum path sum. Path có thể bắt đầu và kết thúc tại bất kỳ node nào — không cần phải đi qua root. Path phải chứa ít nhất 1 node.

Tại sao đây là bài khó?

Path có thể đi qua bất kỳ node nào (không cần root)
Path có thể “bend” tại một node (đi từ left subtree → node → right subtree)
Nhưng khi return lên parent, chỉ có thể chọn một hướng (left hoặc right), không thể bend hai lần

function maxPathSum(root: TreeNode | null): number {
  let globalMax = -Infinity; // Khởi tạo với -Infinity vì values có thể âm
 
  // Returns: max "one-sided" path sum từ node này đi xuống
  // (chỉ có thể chọn left HOẶC right để return về parent)
  function dfs(node: TreeNode | null): number {
    if (!node) return 0;
 
    // Lấy max gain từ left và right subtrees
    // Math.max với 0: nếu subtree sum âm, tốt hơn là không đi xuống đó
    const leftGain = Math.max(dfs(node.left), 0);
    const rightGain = Math.max(dfs(node.right), 0);
 
    // Path qua current node (có thể "bend" ở đây)
    // Đây là candidate cho global maximum
    const pathThroughNode = node.val + leftGain + rightGain;
 
    // Cập nhật global max
    globalMax = Math.max(globalMax, pathThroughNode);
 
    // Return cho parent: chỉ có thể đi một hướng (không bend)
    return node.val + Math.max(leftGain, rightGain);
  }
 
  dfs(root);
  return globalMax;
}
 
// ===== TEST CASES =====
// Tree: [-10, 9, 20, null, null, 15, 7]
//        -10
//        /  \
//       9   20
//          /  \
//         15   7
// Max path: 15 → 20 → 7 = 42
 
// Tree: [-3]
// Max path: -3 (single node, không thể bỏ qua)
// → globalMax phải khởi tạo là -Infinity, không phải 0!
 
// Tree: [1, -2, 3]
// leftGain = max(-2, 0) = 0 (bỏ qua left subtree âm)
// rightGain = max(3, 0) = 3
// pathThrough = 1 + 0 + 3 = 4
// return = 1 + max(0, 3) = 4
 
// ===== COMPLEXITY =====
// Time: O(N) — visit each node once
// Space: O(H) — recursion stack, O(log N) balanced, O(N) skewed

Key Insight cho bài này

Phân biệt hai khái niệm:

“Path through node” = node.val + leftGain + rightGain (để update globalMax — có thể bend)

“Return value to parent” = node.val + max(leftGain, rightGain) (chỉ một hướng — không thể bend lại)

Math.max(gain, 0) là trick để nói “nếu subtree sum âm, tôi chọn không đi xuống đó”.

9. Self-Assessment Checklist

Kiểm tra kiến thức của bạn

DFS Fundamentals:

Viết được inorder/preorder/postorder recursive trong 2 phút
Viết được iterative inorder không cần nhìn gợi ý
Giải thích được tại sao space complexity của DFS là $O (H)$

BFS Fundamentals:

Viết được level order traversal với proper level separation
Giải thích được tại sao levelSize phải được snapshot trước
Biết khi nào BFS tốn nhiều memory hơn DFS

BST:

Giải thích được lỗi khi chỉ check immediate children trong validate BST
Viết được isValidBST với min/max bounds
Viết được lcaBST sử dụng BST property

LCA & Path Problems:

Viết được lcaBinaryTree cho general binary tree
Giải thích được tại sao hasPathSum không thể prune sớm khi có số âm
Giải thích được “bend vs. no-bend” distinction trong #124

Pattern Recognition:

Nhìn đề bài, quyết định được DFS hay BFS trong 30 giây
Biết khi nào dùng postorder (combine results from children)
Hiểu tại sao LCA dùng bottom-up DFS (postorder style)

Tags: dsa tree dfs bfs binary-tree bst faang algorithm Liên quan: 07-Hash-Table | 09-Graph-DFS-BFS | MOC-DSA-Mastery

lthieu's notes

Explorer

08-Tree-DFS-BFS

Buổi 08 — Tree: DFS & BFS

1. Analogy & Context

2. The FAANG Standard

3. Visual Thinking (Mermaid)

3.1 Binary Tree với các level được đánh nhãn

3.2 DFS Traversal Orders — cùng một cây, thứ tự khác nhau

3.3 BFS Level-by-Level với Queue

4. TypeScript Template

4.1 TreeNode Class Definition

4.2 DFS — Inorder, Preorder, Postorder

4.3 BFS — Level Order Traversal

4.4 maxDepth — Recursive $O (N)$

4.5 isValidBST — Min/Max Bounds Approach

4.6 Lowest Common Ancestor (LCA)

4.7 Path Sum — Root-to-Leaf

5. Complexity Deep-dive

Time & Space Complexity

Balanced vs Skewed Trees

Tại sao BFS tốn nhiều space?

6. Edge Cases & Pitfalls

7. Pattern Recognition

8. Top LeetCode Problems

Danh sách theo thứ tự học

Complete Solution: #124 Binary Tree Maximum Path Sum

9. Self-Assessment Checklist

Graph View

Table of Contents

Backlinks

lthieu's notes

Explorer

08-Tree-DFS-BFS

Buổi 08 — Tree: DFS & BFS

1. Analogy & Context

2. The FAANG Standard

3. Visual Thinking (Mermaid)

3.1 Binary Tree với các level được đánh nhãn

3.2 DFS Traversal Orders — cùng một cây, thứ tự khác nhau

3.3 BFS Level-by-Level với Queue

4. TypeScript Template

4.1 TreeNode Class Definition

4.2 DFS — Inorder, Preorder, Postorder

4.3 BFS — Level Order Traversal

4.4 maxDepth — Recursive O(N)

4.5 isValidBST — Min/Max Bounds Approach

4.6 Lowest Common Ancestor (LCA)

4.7 Path Sum — Root-to-Leaf

5. Complexity Deep-dive

Time & Space Complexity

Balanced vs Skewed Trees

Tại sao BFS tốn nhiều space?

6. Edge Cases & Pitfalls

7. Pattern Recognition

8. Top LeetCode Problems

Danh sách theo thứ tự học

Complete Solution: #124 Binary Tree Maximum Path Sum

9. Self-Assessment Checklist

Graph View

Table of Contents

Backlinks

4.4 maxDepth — Recursive $O (N)$