Trees & Binary Trees

What is a Tree?

A tree is a hierarchical data structure with nodes connected by edges. The topmost node is the root, and nodes with no children are leaves. Binary trees have at most 2 children per node.

Tree Traversals

// Inorder (Left, Root, Right) - Gives sorted order in BST
function inorder(root, result = []) {
  if (!root) return result;
  inorder(root.left, result);
  result.push(root.value);
  inorder(root.right, result);
  return result;
}

// Preorder (Root, Left, Right)
function preorder(root, result = []) {
  if (!root) return result;
  result.push(root.value);
  preorder(root.left, result);
  preorder(root.right, result);
  return result;
}

// Postorder (Left, Right, Root)
function postorder(root, result = []) {
  if (!root) return result;
  postorder(root.left, result);
  postorder(root.right, result);
  result.push(root.value);
  return result;
}

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