Trees & Binary Trees

What is a Tree?

A tree is a hierarchical data structure consisting of nodes connected by edges. Unlike arrays or linked lists (which are linear), trees branch outward, making them ideal for representing hierarchical relationships such as file systems, organization charts, and HTML DOMs.

• Root: The topmost node with no parent.
• Leaf: A node with no children.
• Height: Length of the longest path from root to a leaf.
• Depth: Distance from the root to a given node.
• Subtree: A node and all its descendants.

Binary Trees

A binary tree is a tree where each node has at most two children, called the left child and right child. A full binary tree has every node with 0 or 2 children. A complete binary tree fills every level except possibly the last, which fills left to right.

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

// Build a small tree manually
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);
//        1
//       / \
//      2   3
//     / \
//    4   5

Tree Traversals

Traversal order determines the order in which nodes are visited. Each type has different use cases.

// Inorder: Left → Root → Right
// Use case: produces sorted output for a 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
// Use case: serialize/clone a tree
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
// Use case: delete a tree, evaluate expression trees
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): level by level
// Use case: find the shortest path, print tree level by level
function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];

  while (queue.length) {
    const level = [];
    const size = queue.length;   // process current level

    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;
}

// Test
inorder(root);    // [4, 2, 5, 1, 3]
preorder(root);   // [1, 2, 4, 5, 3]
postorder(root);  // [4, 5, 2, 3, 1]
levelOrder(root); // [[1], [2, 3], [4, 5]]

Iterative Inorder Traversal

Recursive traversals can overflow the call stack on very deep trees. An iterative version uses an explicit stack:

function inorderIterative(root) {
  const result = [];
  const stack = [];
  let current = root;

  while (current || stack.length) {
    // Go as far left as possible
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    result.push(current.value);
    current = current.right;
  }
  return result;
}