Trees & Binary Search Trees: Cấu Trúc Dữ Liệu Phân Cấp

// TypeScript - Binary Tree Node
class TreeNode<T> {
  val: T;
  left: TreeNode<T> | null;
  right: TreeNode<T> | null;
 
  constructor(val: T, left: TreeNode<T> | null = null, right: TreeNode<T> | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}
 
// Xây dựng tree thủ công
const root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(15);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(7);
root.right.left = new TreeNode(12);
root.right.right = new TreeNode(20);

# Python - Binary Tree Node
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
# Xây dựng tree thủ công
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.left = TreeNode(12)
root.right.right = TreeNode(20)

// TypeScript - Duyệt Inorder
 
// Đệ quy (sạch sẽ và trực quan)
function inorderRecursive(root: TreeNode<number> | null): number[] {
  const result: number[] = [];
 
  function dfs(node: TreeNode<number> | null): void {
    if (!node) return;
    dfs(node.left);        // Trái
    result.push(node.val); // Root
    dfs(node.right);       // Phải
  }
 
  dfs(root);
  return result;
}
 
// Vòng lặp (dùng stack tường minh — quan trọng cho phỏng vấn)
function inorderIterative(root: TreeNode<number> | null): number[] {
  const result: number[] = [];
  const stack: TreeNode<number>[] = [];
  let current = root;
 
  while (current || stack.length > 0) {
    // Đi sang trái xa nhất có thể
    while (current) {
      stack.push(current);
      current = current.left;
    }
    // Xử lý node hiện tại
    current = stack.pop()!;
    result.push(current.val);
    // Chuyển sang subtree phải
    current = current.right;
  }
 
  return result;
}

# Python - Duyệt Inorder
 
# Đệ quy
def inorder_recursive(root: TreeNode | None) -> list[int]:
    result = []
 
    def dfs(node: TreeNode | None):
        if not node:
            return
        dfs(node.left)           # Trái
        result.append(node.val)  # Root
        dfs(node.right)          # Phải
 
    dfs(root)
    return result
 
# Vòng lặp
def inorder_iterative(root: TreeNode | None) -> list[int]:
    result = []
    stack = []
    current = root
 
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
 
    return result

// TypeScript - Duyệt Preorder
 
// Đệ quy
function preorderRecursive(root: TreeNode<number> | null): number[] {
  const result: number[] = [];
 
  function dfs(node: TreeNode<number> | null): void {
    if (!node) return;
    result.push(node.val); // Root
    dfs(node.left);        // Trái
    dfs(node.right);       // Phải
  }
 
  dfs(root);
  return result;
}
 
// Vòng lặp
function preorderIterative(root: TreeNode<number> | null): number[] {
  if (!root) return [];
  const result: number[] = [];
  const stack: TreeNode<number>[] = [root];
 
  while (stack.length > 0) {
    const node = stack.pop()!;
    result.push(node.val);
    // Push phải trước để trái được xử lý trước (stack là LIFO)
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
 
  return result;
}

# Python - Duyệt Preorder
 
# Đệ quy
def preorder_recursive(root: TreeNode | None) -> list[int]:
    result = []
 
    def dfs(node: TreeNode | None):
        if not node:
            return
        result.append(node.val)  # Root
        dfs(node.left)           # Trái
        dfs(node.right)          # Phải
 
    dfs(root)
    return result
 
# Vòng lặp
def preorder_iterative(root: TreeNode | None) -> list[int]:
    if not root:
        return []
    result = []
    stack = [root]
 
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
 
    return result

// TypeScript - Duyệt Postorder
 
// Đệ quy
function postorderRecursive(root: TreeNode<number> | null): number[] {
  const result: number[] = [];
 
  function dfs(node: TreeNode<number> | null): void {
    if (!node) return;
    dfs(node.left);        // Trái
    dfs(node.right);       // Phải
    result.push(node.val); // Root
  }
 
  dfs(root);
  return result;
}
 
// Vòng lặp (preorder biến đổi + đảo ngược)
function postorderIterative(root: TreeNode<number> | null): number[] {
  if (!root) return [];
  const result: number[] = [];
  const stack: TreeNode<number>[] = [root];
 
  while (stack.length > 0) {
    const node = stack.pop()!;
    result.push(node.val);
    // Push trái trước, rồi phải (ngược với preorder)
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }
 
  return result.reverse(); // Đảo ngược cho ra postorder
}

# Python - Duyệt Postorder
 
# Đệ quy
def postorder_recursive(root: TreeNode | None) -> list[int]:
    result = []
 
    def dfs(node: TreeNode | None):
        if not node:
            return
        dfs(node.left)           # Trái
        dfs(node.right)          # Phải
        result.append(node.val)  # Root
 
    dfs(root)
    return result
 
# Vòng lặp (preorder biến đổi + đảo ngược)
def postorder_iterative(root: TreeNode | None) -> list[int]:
    if not root:
        return []
    result = []
    stack = [root]
 
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
 
    return result[::-1]

// TypeScript - Duyệt Level-Order (BFS)
function levelOrder(root: TreeNode<number> | null): number[][] {
  if (!root) return [];
  const result: number[][] = [];
  const queue: TreeNode<number>[] = [root];
 
  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel: number[] = [];
 
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      currentLevel.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
 
    result.push(currentLevel);
  }
 
  return result;
  // Trả về: [[10], [5, 15], [3, 7, 12, 20]]
}

# Python - Duyệt Level-Order (BFS)
from collections import deque
 
def level_order(root: TreeNode | None) -> list[list[int]]:
    if not root:
        return []
    result = []
    queue = deque([root])
 
    while queue:
        level_size = len(queue)
        current_level = []
 
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
 
        result.append(current_level)
 
    return result
    # Trả về: [[10], [5, 15], [3, 7, 12, 20]]

// TypeScript - Tìm kiếm BST
 
// Đệ quy
function searchBST(root: TreeNode<number> | null, target: number): TreeNode<number> | null {
  if (!root) return null;
  if (target === root.val) return root;
  if (target < root.val) return searchBST(root.left, target);
  return searchBST(root.right, target);
}
 
// Vòng lặp (ưu tiên — không có risk stack overflow)
function searchBSTIterative(root: TreeNode<number> | null, target: number): TreeNode<number> | null {
  let current = root;
  while (current) {
    if (target === current.val) return current;
    if (target < current.val) current = current.left;
    else current = current.right;
  }
  return null;
}

# Python - Tìm kiếm BST
 
# Đệ quy
def search_bst(root: TreeNode | None, target: int) -> TreeNode | None:
    if not root:
        return None
    if target == root.val:
        return root
    if target < root.val:
        return search_bst(root.left, target)
    return search_bst(root.right, target)
 
# Vòng lặp
def search_bst_iterative(root: TreeNode | None, target: int) -> TreeNode | None:
    current = root
    while current:
        if target == current.val:
            return current
        elif target < current.val:
            current = current.left
        else:
            current = current.right
    return None

// TypeScript - Chèn BST
function insertBST(root: TreeNode<number> | null, val: number): TreeNode<number> {
  if (!root) return new TreeNode(val);
 
  if (val < root.val) {
    root.left = insertBST(root.left, val);
  } else if (val > root.val) {
    root.right = insertBST(root.right, val);
  }
  // Nếu val === root.val, bỏ qua duplicate
 
  return root;
}

# Python - Chèn BST
def insert_bst(root: TreeNode | None, val: int) -> TreeNode:
    if not root:
        return TreeNode(val)
 
    if val < root.val:
        root.left = insert_bst(root.left, val)
    elif val > root.val:
        root.right = insert_bst(root.right, val)
 
    return root

// TypeScript - Xóa BST
function deleteBST(root: TreeNode<number> | null, val: number): TreeNode<number> | null {
  if (!root) return null;
 
  if (val < root.val) {
    root.left = deleteBST(root.left, val);
  } else if (val > root.val) {
    root.right = deleteBST(root.right, val);
  } else {
    // Tìm thấy node cần xóa
 
    // Trường hợp 1 & 2: Không có child hoặc một child
    if (!root.left) return root.right;
    if (!root.right) return root.left;
 
    // Trường hợp 3: Hai children — tìm inorder successor
    let successor = root.right;
    while (successor.left) {
      successor = successor.left;
    }
    root.val = successor.val;
    root.right = deleteBST(root.right, successor.val);
  }
 
  return root;
}

# Python - Xóa BST
def delete_bst(root: TreeNode | None, val: int) -> TreeNode | None:
    if not root:
        return None
 
    if val < root.val:
        root.left = delete_bst(root.left, val)
    elif val > root.val:
        root.right = delete_bst(root.right, val)
    else:
        # Tìm thấy node cần xóa
 
        # Trường hợp 1 & 2: Không có child hoặc một child
        if not root.left:
            return root.right
        if not root.right:
            return root.left
 
        # Trường hợp 3: Hai children — tìm inorder successor
        successor = root.right
        while successor.left:
            successor = successor.left
        root.val = successor.val
        root.right = delete_bst(root.right, successor.val)
 
    return root

// TypeScript - Cài Đặt Trie Cơ Bản
class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEnd: boolean = false;
}
 
class Trie {
  root: TrieNode = new TrieNode();
 
  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.isEnd = true;
  }
 
  search(word: string): boolean {
    const node = this.findNode(word);
    return node !== null && node.isEnd;
  }
 
  startsWith(prefix: string): boolean {
    return this.findNode(prefix) !== null;
  }
 
  private findNode(prefix: string): TrieNode | null {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) return null;
      node = node.children.get(char)!;
    }
    return node;
  }
}
 
// Sử dụng
const trie = new Trie();
trie.insert("car");
trie.insert("cat");
trie.insert("dog");
console.log(trie.search("car"));      // true
console.log(trie.search("ca"));       // false
console.log(trie.startsWith("ca"));   // true

# Python - Cài Đặt Trie Cơ Bản
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
 
class Trie:
    def __init__(self):
        self.root = TrieNode()
 
    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
 
    def search(self, word: str) -> bool:
        node = self._find_node(word)
        return node is not None and node.is_end
 
    def starts_with(self, prefix: str) -> bool:
        return self._find_node(prefix) is not None
 
    def _find_node(self, prefix: str) -> TrieNode | None:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

// TypeScript - Độ Sâu Tối Đa
function maxDepth(root: TreeNode<number> | null): number {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
// Tree: [10, 5, 15, 3, 7] → maxDepth = 3

# Python - Độ Sâu Tối Đa
def max_depth(root: TreeNode | None) -> int:
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

// TypeScript - Lật Binary Tree
function invertTree(root: TreeNode<number> | null): TreeNode<number> | null {
  if (!root) return null;
 
  // Đổi children
  const temp = root.left;
  root.left = root.right;
  root.right = temp;
 
  // Đệ quy
  invertTree(root.left);
  invertTree(root.right);
 
  return root;
}

# Python - Lật Binary Tree
def invert_tree(root: TreeNode | None) -> TreeNode | None:
    if not root:
        return None
 
    root.left, root.right = root.right, root.left
 
    invert_tree(root.left)
    invert_tree(root.right)
 
    return root

// TypeScript - Kiểm Tra BST
function isValidBST(root: TreeNode<number> | null): boolean {
  function validate(
    node: TreeNode<number> | 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) &&
      validate(node.right, node.val, max)
    );
  }
 
  return validate(root, -Infinity, Infinity);
}

# Python - Kiểm Tra BST
def is_valid_bst(root: TreeNode | None) -> bool:
    def validate(node: TreeNode | None, min_val: float, max_val: float) -> bool:
        if not node:
            return True
        if node.val <= min_val or node.val >= max_val:
            return False
        return (
            validate(node.left, min_val, node.val) and
            validate(node.right, node.val, max_val)
        )
 
    return validate(root, float('-inf'), float('inf'))

// TypeScript - LCA của Binary Tree
function lowestCommonAncestor(
  root: TreeNode<number> | null,
  p: TreeNode<number>,
  q: TreeNode<number>
): TreeNode<number> | null {
  if (!root || root === p || root === q) return root;
 
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
 
  // Nếu cả hai bên trả về non-null, root là LCA
  if (left && right) return root;
  // Ngược lại, LCA ở bên trả về non-null
  return left ?? right;
}
 
// Cho BST — tận dụng tính chất sắp xếp
function lcaBST(
  root: TreeNode<number> | null,
  p: TreeNode<number>,
  q: TreeNode<number>
): TreeNode<number> | null {
  if (!root) return null;
 
  if (p.val < root.val && q.val < root.val) {
    return lcaBST(root.left, p, q);    // Cả hai bên trái
  }
  if (p.val > root.val && q.val > root.val) {
    return lcaBST(root.right, p, q);   // Cả hai bên phải
  }
  return root; // Điểm chia — đây là LCA
}

# Python - LCA của Binary Tree
def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root
 
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
 
    if left and right:
        return root
    return left or right
 
# Cho BST
def lca_bst(root, p, q):
    if not root:
        return None
    if p.val < root.val and q.val < root.val:
        return lca_bst(root.left, p, q)
    if p.val > root.val and q.val > root.val:
        return lca_bst(root.right, p, q)
    return root

// TypeScript - Kiểm Tra Balanced
function isBalanced(root: TreeNode<number> | null): boolean {
  function height(node: TreeNode<number> | null): number {
    if (!node) return 0;
 
    const leftHeight = height(node.left);
    if (leftHeight === -1) return -1; // Subtree trái không balanced
 
    const rightHeight = height(node.right);
    if (rightHeight === -1) return -1; // Subtree phải không balanced
 
    if (Math.abs(leftHeight - rightHeight) > 1) return -1; // Node hiện tại không balanced
 
    return 1 + Math.max(leftHeight, rightHeight);
  }
 
  return height(root) !== -1;
}

# Python - Kiểm Tra Balanced
def is_balanced(root: TreeNode | None) -> bool:
    def height(node: TreeNode | None) -> int:
        if not node:
            return 0
 
        left_h = height(node.left)
        if left_h == -1:
            return -1
 
        right_h = height(node.right)
        if right_h == -1:
            return -1
 
        if abs(left_h - right_h) > 1:
            return -1
 
        return 1 + max(left_h, right_h)
 
    return height(root) != -1

// TypeScript - Path Sum
function hasPathSum(root: TreeNode<number> | null, targetSum: number): boolean {
  if (!root) return false;
 
  // Leaf node — kiểm tra tổng còn lại có bằng giá trị node này không
  if (!root.left && !root.right) {
    return targetSum === root.val;
  }
 
  const remaining = targetSum - root.val;
  return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
}

# Python - Path Sum
def has_path_sum(root: TreeNode | None, target_sum: int) -> bool:
    if not root:
        return False
 
    if not root.left and not root.right:
        return target_sum == root.val
 
    remaining = target_sum - root.val
    return has_path_sum(root.left, remaining) or has_path_sum(root.right, remaining)

// TypeScript - Serialize/Deserialize (Preorder)
function serialize(root: TreeNode<number> | null): string {
  const result: string[] = [];
 
  function dfs(node: TreeNode<number> | null): void {
    if (!node) {
      result.push("null");
      return;
    }
    result.push(String(node.val));
    dfs(node.left);
    dfs(node.right);
  }
 
  dfs(root);
  return result.join(",");
}
 
function deserialize(data: string): TreeNode<number> | null {
  const values = data.split(",");
  let index = 0;
 
  function dfs(): TreeNode<number> | null {
    if (values[index] === "null") {
      index++;
      return null;
    }
 
    const node = new TreeNode(Number(values[index]));
    index++;
    node.left = dfs();
    node.right = dfs();
    return node;
  }
 
  return dfs();
}

# Python - Serialize/Deserialize (Preorder)
def serialize(root: TreeNode | None) -> str:
    result = []
 
    def dfs(node):
        if not node:
            result.append("null")
            return
        result.append(str(node.val))
        dfs(node.left)
        dfs(node.right)
 
    dfs(root)
    return ",".join(result)
 
def deserialize(data: str) -> TreeNode | None:
    values = iter(data.split(","))
 
    def dfs():
        val = next(values)
        if val == "null":
            return None
        node = TreeNode(int(val))
        node.left = dfs()
        node.right = dfs()
        return node
 
    return dfs()

// TypeScript - Xây Tree từ Preorder + Inorder
function buildTree(preorder: number[], inorder: number[]): TreeNode<number> | null {
  const inorderMap = new Map<number, number>();
  inorder.forEach((val, idx) => inorderMap.set(val, idx));
 
  let preIdx = 0;
 
  function build(left: number, right: number): TreeNode<number> | null {
    if (left > right) return null;
 
    const rootVal = preorder[preIdx++];
    const root = new TreeNode(rootVal);
    const mid = inorderMap.get(rootVal)!;
 
    root.left = build(left, mid - 1);
    root.right = build(mid + 1, right);
 
    return root;
  }
 
  return build(0, inorder.length - 1);
}

# Python - Xây Tree từ Preorder + Inorder
def build_tree(preorder: list[int], inorder: list[int]) -> TreeNode | None:
    inorder_map = {val: idx for idx, val in enumerate(inorder)}
    pre_idx = [0]  # Dùng list để cho phép thay đổi trong nested function
 
    def build(left: int, right: int) -> TreeNode | None:
        if left > right:
            return None
 
        root_val = preorder[pre_idx[0]]
        pre_idx[0] += 1
        root = TreeNode(root_val)
        mid = inorder_map[root_val]
 
        root.left = build(left, mid - 1)
        root.right = build(mid + 1, right)
 
        return root
 
    return build(0, len(inorder) - 1)