Tree
Binary Tree, BST, Trie

9.1 Terminology — thuật ngữ cần thuộc

           [10]              ← root (gốc)
          /    \
        [5]    [15]            ← internal nodes
        / \      \
      [3] [7]   [20]           ← leaves (lá) — không có con

- Root:   node trên cùng, không có parent
- Leaf:   node không có con (cả trái lẫn phải đều null)
- Parent: node "cha" (level trên)
- Child:  node "con" (level dưới)
- Sibling: cùng parent
- Depth:  khoảng cách từ root đến node (root depth = 0)
- Height: khoảng cách từ node đến leaf xa nhất
- Level:  depth + 1 (đôi khi cùng nghĩa)
- Subtree: cây con bắt nguồn từ một node

Phân loại Binary Tree

• Full: mọi node có 0 hoặc 2 con (không có node có 1 con duy nhất)
• Complete: tất cả các level đều đầy, ngoại trừ level cuối có thể chưa đầy nhưng được fill từ trái sang phải
• Perfect: full + tất cả leaves cùng level
• Balanced: chiều cao giữa nhánh trái và phải của mỗi node chênh nhau ≤ 1 → cây "thấp", thao tác hiệu quả
• Skewed: như linked list — mọi node chỉ có 1 con

9.2 Binary Tree — cài đặt cơ bản

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

// Tạo cây thủ công:
//        1
//       / \
//      2   3
//     / \
//    4   5
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

Tính chiều cao (height) của cây

// Height = số cạnh dài nhất từ node đến leaf
function height(root) {
  if (!root) return -1;  // hoặc 0, tuỳ định nghĩa
  return 1 + Math.max(height(root.left), height(root.right));
}

// Hoặc đếm theo số node (depth-based):
function maxDepth(root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Đếm số node

function countNodes(root) {
  if (!root) return 0;
  return 1 + countNodes(root.left) + countNodes(root.right);
}

9.3 Traversal (DFS) — 3 thứ tự cần thuộc

3 cách duyệt cây theo DFS, khác nhau ở thứ tự thăm node:

• Pre-order: Node → Trái → Phải
• In-order: Trái → Node → Phải
• Post-order: Trái → Phải → Node

           1
          / \
         2   3
        / \
       4   5

Pre-order:  1, 2, 4, 5, 3
In-order:   4, 2, 5, 1, 3
Post-order: 4, 5, 2, 3, 1

9.3.1 Recursive — đẹp và dễ hiểu

function preOrder(root, result = []) {
  if (!root) return result;
  result.push(root.val);
  preOrder(root.left, result);
  preOrder(root.right, result);
  return result;
}

function inOrder(root, result = []) {
  if (!root) return result;
  inOrder(root.left, result);
  result.push(root.val);
  inOrder(root.right, result);
  return result;
}

function postOrder(root, result = []) {
  if (!root) return result;
  postOrder(root.left, result);
  postOrder(root.right, result);
  result.push(root.val);
  return result;
}

9.3.2 Iterative với Stack — bắt buộc biết

// Pre-order iterative
function preOrderIter(root) {
  if (!root) return [];
  const result = [], stack = [root];
  while (stack.length) {
    const node = stack.pop();
    result.push(node.val);
    if (node.right) stack.push(node.right);  // right trước vì stack LIFO
    if (node.left)  stack.push(node.left);
  }
  return result;
}

// In-order iterative — tricky hơn
function inOrderIter(root) {
  const result = [], stack = [];
  let curr = root;
  while (curr || stack.length) {
    while (curr) {
      stack.push(curr);
      curr = curr.left;
    }
    curr = stack.pop();
    result.push(curr.val);
    curr = curr.right;
  }
  return result;
}

// Post-order iterative — khó nhất
function postOrderIter(root) {
  if (!root) return [];
  const result = [], stack = [root];
  while (stack.length) {
    const node = stack.pop();
    result.unshift(node.val);  // chèn đầu (đảo thứ tự pre-order)
    if (node.left)  stack.push(node.left);
    if (node.right) stack.push(node.right);
  }
  return result;
}
// Trick: post-order = đảo ngược của (Node → Right → Left)

Khi nào dùng cái nào?

9.4 Level-order Traversal (BFS) — duyệt theo lớp

Thăm node theo từng level — root → tất cả depth=1 → tất cả depth=2 → ...

function levelOrder(root) {
  if (!root) return [];
  const result = [], queue = [root];
  while (queue.length) {
    const level = [];
    const sz = queue.length;  // số node ở level hiện tại
    for (let i = 0; i < sz; i++) {
      const node = queue.shift();  // (Lưu ý: shift O(n), demo thôi)
      level.push(node.val);
      if (node.left)  queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

//        1
//       / \
//      2   3
//     / \
//    4   5
// Output: [[1], [2,3], [4,5]]

Variants của Level-order

• Zigzag: level chẵn trái-phải, level lẻ phải-trái
• Right Side View: trả về phần tử phải nhất của mỗi level
• Average of Levels: tính trung bình mỗi level

// Right Side View
function rightSideView(root) {
  if (!root) return [];
  const result = [], queue = [root];
  while (queue.length) {
    const sz = queue.length;
    for (let i = 0; i < sz; i++) {
      const node = queue.shift();
      if (i === sz - 1) result.push(node.val);  // cuối level
      if (node.left)  queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return result;
}

9.5 Binary Search Tree (BST) — cây tìm kiếm nhị phân

Định nghĩa BST: với mỗi node:

• Mọi node trong subtree trái có giá trị < node hiện tại
• Mọi node trong subtree phải có giá trị > node hiện tại
• (Tuỳ định nghĩa, có thể cho phép = hoặc không — thường BST chuẩn không cho phép trùng)

           [8]
          /   \
        [3]   [10]
        / \      \
      [1] [6]   [14]
          / \    /
        [4] [7] [13]

BST là cây "tự sort": in-order traversal của BST cho ra mảng tăng dần.

Tính chất BẤT ĐẲNG QUAN TRỌNG

// ❌ SAI — chỉ check 1 cấp
function isValidBSTBad(root) {
  if (!root) return true;
  if (root.left && root.left.val >= root.val) return false;
  if (root.right && root.right.val <= root.val) return false;
  return isValidBSTBad(root.left) && isValidBSTBad(root.right);
}
// Counter-example:
//      5
//     / \
//    3   8
//       /
//      2     ← 2 < 5 nhưng nằm trong right subtree → vi phạm!

// ✅ ĐÚNG — truyền (min, max) xuống
function isValidBST(root, min = -Infinity, max = Infinity) {
  if (!root) return true;
  if (root.val <= min || root.val >= max) return false;
  return isValidBST(root.left, min, root.val) &&
         isValidBST(root.right, root.val, max);
}

// ✅ ĐÚNG — dùng in-order traversal (cho ra phải sort tăng)
function isValidBSTInorder(root) {
  let prev = -Infinity;
  function inorder(node) {
    if (!node) return true;
    if (!inorder(node.left)) return false;
    if (node.val <= prev) return false;
    prev = node.val;
    return inorder(node.right);
  }
  return inorder(root);
}

9.6 BST Operations — search, insert, delete

Search — O(h) với h là height

function search(root, target) {
  if (!root) return null;
  if (root.val === target) return root;
  if (target < root.val) return search(root.left, target);
  return search(root.right, target);
}

Insert

function insert(root, val) {
  if (!root) return new TreeNode(val);
  if (val < root.val) root.left = insert(root.left, val);
  else if (val > root.val) root.right = insert(root.right, val);
  // val === root.val: bỏ qua (BST không cho trùng)
  return root;
}

Delete — phức tạp nhất, 3 trường hợp

function deleteNode(root, key) {
  if (!root) return null;

  if (key < root.val) {
    root.left = deleteNode(root.left, key);
  } else if (key > root.val) {
    root.right = deleteNode(root.right, key);
  } else {
    // Tìm thấy node cần xoá
    // Case 1: leaf — chỉ cần xoá
    if (!root.left && !root.right) return null;
    // Case 2: chỉ có 1 con — thay bằng con đó
    if (!root.left)  return root.right;
    if (!root.right) return root.left;
    // Case 3: có 2 con — thay bằng successor (nhỏ nhất ở right subtree)
    let succ = root.right;
    while (succ.left) succ = succ.left;
    root.val = succ.val;
    root.right = deleteNode(root.right, succ.val);
  }
  return root;
}

Tại sao chọn successor? Vì successor là phần tử vừa lớn hơn node bị xoá → giữ tính chất BST.

Big-O của BST operations

Worst O(n) xảy ra khi BST suy biến thành linked list (vd insert 1, 2, 3, 4, 5 theo thứ tự). Để tránh, ta cần self-balancing BST.

9.7 Balanced BST — AVL, Red-Black

Self-balancing BST tự động giữ height ~O(log n) bằng cách xoay (rotation) sau insert/delete. Bạn không cần cài chi tiết, nhưng phải biết tên + nguyên lý.

AVL Tree (1962)

• Mỗi node lưu "balance factor" = height(left) - height(right)
• Yêu cầu balance factor luôn ∈ {-1, 0, 1}
• Khi insert/delete, nếu vi phạm → rotate (LL, LR, RL, RR)
• Strict balance → search nhanh nhất, nhưng nhiều rotation

Red-Black Tree

• Mỗi node có "màu" đỏ hoặc đen, với 5 invariants
• Balance "lỏng" hơn AVL — chiều cao có thể lệch nhưng không vượt 2x
• Ít rotation hơn → insert/delete nhanh hơn
• Java TreeMap, C++ std::map, Linux kernel scheduler đều dùng

B-tree / B+ tree

• Cây có nhiều con (không chỉ 2) — phù hợp disk-based storage
• Database index (MySQL InnoDB B+ tree), filesystem (NTFS, HFS+)
• Giảm số lần đọc disk vì 1 page chứa nhiều keys

9.8 Trie (Prefix Tree) — vũ khí cho string

Trie (đọc là "try", từ "retrieval") là cây mà mỗi cạnh đại diện 1 ký tự, mỗi đường từ root đến leaf tạo thành 1 từ. Cực kỳ tốt cho:

• Autocomplete
• Spell check
• IP routing (longest prefix match)
• Bài "search by prefix"

            [root]
           /   |   \
          a    b    c
         / \   |
        p   t  e
        |   |  |
        p   ●  e
        |      |
        l      ●
        |
        e
        |
        ●

(các ● = end of word: "app", "at", "be", "bee")

Cài đặt Trie

class TrieNode {
  constructor() {
    this.children = {};   // hoặc Map(), hoặc Array(26) cho a-z
    this.isEnd = false;
  }
}

class Trie {
  constructor() { this.root = new TrieNode(); }

  // O(L) với L = độ dài từ
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch];
    }
    node.isEnd = true;
  }

  search(word) {
    const node = this._traverse(word);
    return node !== null && node.isEnd;
  }

  startsWith(prefix) {
    return this._traverse(prefix) !== null;
  }

  _traverse(s) {
    let node = this.root;
    for (const ch of s) {
      if (!node.children[ch]) return null;
      node = node.children[ch];
    }
    return node;
  }
}

// Demo
const t = new Trie();
t.insert("apple");
t.insert("app");
console.log(t.search("apple"));    // true
console.log(t.search("app"));      // true
console.log(t.search("ap"));       // false (không phải end)
console.log(t.startsWith("ap"));   // true

Big-O của Trie

• Insert / Search / startsWith: O(L) với L = độ dài word/prefix
• Space: O(N · L) tệ nhất, nhưng tiết kiệm khi nhiều từ chia sẻ prefix

Ưu điểm so với HashSet<String>

• HashSet: O(L) search nhưng không hỗ trợ prefix
• Trie: O(L) search + O(L) prefix search → autocomplete cực nhanh

9.9 LCA & Diameter — bài kinh điển

9.9.1 Lowest Common Ancestor

Tìm ancestor (tổ tiên) thấp nhất của 2 node p, q.

// Cho cây bất kỳ (không cần BST)
function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left  = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;  // p và q ở 2 subtree khác nhau
  return left || right;
}

// Trong BST có thể tận dụng tính chất sort
function lcaBST(root, p, q) {
  if (p.val < root.val && q.val < root.val) return lcaBST(root.left, p, q);
  if (p.val > root.val && q.val > root.val) return lcaBST(root.right, p, q);
  return root;  // p và q nằm hai bên hoặc chính là root
}

9.9.2 Diameter of Binary Tree

Đường đi dài nhất giữa 2 node bất kỳ (không nhất thiết qua root).

function diameter(root) {
  let max = 0;
  function depth(node) {
    if (!node) return 0;
    const l = depth(node.left);
    const r = depth(node.right);
    max = Math.max(max, l + r);  // đường đi qua node = l + r
    return 1 + Math.max(l, r);
  }
  depth(root);
  return max;
}

9.9.3 Serialize and Deserialize Tree

// Serialize: dùng pre-order với marker null
function serialize(root) {
  const result = [];
  function dfs(node) {
    if (!node) { result.push('#'); return; }
    result.push(node.val);
    dfs(node.left);
    dfs(node.right);
  }
  dfs(root);
  return result.join(',');
}

function deserialize(data) {
  const tokens = data.split(',');
  let i = 0;
  function build() {
    const t = tokens[i++];
    if (t === '#') return null;
    const node = new TreeNode(Number(t));
    node.left  = build();
    node.right = build();
    return node;
  }
  return build();
}

Bài tập

Tổng kết chương 9

• ✅ Tree terminology: root, leaf, depth, height, level
• ✅ 4 traversal: Pre/In/Post-order (DFS) và Level-order (BFS)
• ✅ Iterative traversal dùng Stack (DFS) hoặc Queue (BFS) — phải biết cả recursive lẫn iterative
• ✅ BST: in-order = sorted; search/insert/delete O(log n) avg, O(n) worst
• ✅ Validate BST phải kiểm tra với min/max bound, không chỉ 1 cấp
• ✅ Delete node 2 con: thay bằng successor
• ✅ AVL / Red-Black tree = self-balancing BST cho O(log n) đảm bảo
• ✅ Trie: O(L) insert/search/prefix — vũ khí autocomplete
• ✅ Bài kinh điển: LCA, Diameter, Serialize tree