Binary Trees

What Is a Binary Tree?

A binary tree is a tree where every node has at most two children. That's it. They're called the left child and the right child. It's like a regular tree, but with a strict rule: no node can have more than two kids.

This simplicity is what makes binary trees so powerful. With at most two branches at each step, algorithms can make quick decisions — go left or go right. That cuts your search space in half every time.

Binary trees are the foundation for some of the most important data structures in computer science. BSTs, heaps, and tries all build on this basic idea.

Types of Binary Trees

A full binary tree is one where every node has either zero or two children. No node has just one child. Think of it like a branching system where every split creates exactly two paths.

A complete binary tree fills every level completely before starting a new one, and all nodes in the last level are as far left as possible. Heaps use this property to store data efficiently in an array.

A perfect binary tree is both full and complete — every level is completely filled. A tree with depth d has exactly 2^(d+1) - 1 nodes. They're beautiful but rare in practice.

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

const root = new BinaryTreeNode(1);
root.left = new BinaryTreeNode(2);
root.right = new BinaryTreeNode(3);
root.left.left = new BinaryTreeNode(4);
root.left.right = new BinaryTreeNode(5);

Height and Depth

The height of a tree is the number of edges on the longest path from the root to a leaf. A single node has height 0. A tree with just a root and two children has height 1.

The depth of a node is the number of edges from the root to that node. The root has depth 0. Its children have depth 1, and so on. Height and depth are inverses — the height of a tree equals the maximum depth of any node.

Why do these matter? Because the height of a binary tree determines how fast operations can be. A balanced tree with n nodes has height log(n). A skewed tree (like a linked list) has height n. That's the difference between fast and slow.

function getHeight(node) {
  if (!node) return -1;
  const leftH = getHeight(node.left);
  const rightH = getHeight(node.right);
  return 1 + Math.max(leftH, rightH);
}

function getDepth(root, target, depth = 0) {
  if (!root) return -1;
  if (root.value === target) return depth;
  const left = getDepth(root.left, target, depth + 1);
  if (left !== -1) return left;
  return getDepth(root.right, target, depth + 1);
}

console.log(getHeight(root));
console.log(getDepth(root, 5));