Algorithms Lesson 6: Trees

Trees are hierarchical data structures. They appear everywhere: file systems, DOM, JSON, database indexes, decision trees in ML, and syntax trees in compilers.

Tree Traversals

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

// In-order: Left → Root → Right (gives sorted order for BST!)
function inOrder(node, result = []) {
  if (!node) return result;
  inOrder(node.left, result);
  result.push(node.val);
  inOrder(node.right, result);
  return result;
}

// Pre-order: Root → Left → Right (for copying trees)
function preOrder(node, result = []) {
  if (!node) return result;
  result.push(node.val);
  preOrder(node.left, result);
  preOrder(node.right, result);
  return result;
}

// Post-order: Left → Right → Root (for deleting trees)
function postOrder(node, result = []) {
  if (!node) return result;
  postOrder(node.left, result);
  postOrder(node.right, result);
  result.push(node.val);
  return result;
}

// BFS — Level Order Traversal
function levelOrder(root) {
  if (!root) return [];
  const queue = [root], result = [];
  while (queue.length) {
    const level = [];
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}