Binary Trees

A binary tree is a tree in which every node has at most two children, conventionally called the left child and the right child. This two-child limit sounds simple, but it enables a large family of efficient algorithms — binary search trees, heaps, segment trees, and more all rest on this foundation.

Standard Node Class

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

// Build: 1 -> left: 2, right: 3; node 2 -> left: 4
const root = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), null),
  new TreeNode(3),
);

Shape Variants

Real problems often specify a particular shape. The four most common:

Full binary tree — every node has 0 or 2 children; no node has exactly one child.

Complete binary tree — all levels are fully filled except possibly the last, which is filled left to right. Heaps use this shape.

Perfect binary tree — every internal node has exactly 2 children and all leaves are at the same depth. A perfect tree with height h has 2^(h+1) - 1 nodes.

Balanced binary tree — the height difference between the left and right subtrees of every node is at most 1 (the formal AVL definition). A balanced tree with n nodes has height O(log n), which is why balanced BSTs guarantee O(log n) operations.

Linked Representation

The TreeNode class above is the linked representation. Each node holds its value and references to its two children. Building or modifying the tree requires only pointer updates — no reallocation.

Array (Heap-Style) Representation

A complete binary tree maps cleanly onto a flat array using 1-based indexing:

• Root at index 1.
• Left child of node at index i → index 2 * i.
• Right child of node at index i → index 2 * i + 1.
• Parent of node at index i → index Math.floor(i / 2).

// Tree:        1
//            /   \
//           2     3
//          / \   /
//         4   5 6
//
// Array (index 0 unused): [_, 1, 2, 3, 4, 5, 6]

const tree = [undefined, 1, 2, 3, 4, 5, 6];

function leftChild(i)  { return 2 * i; }
function rightChild(i) { return 2 * i + 1; }
function parent(i)     { return Math.floor(i / 2); }

console.log(tree[leftChild(2)]);  // 4  (left child of node 2)
console.log(tree[parent(5)]);     // 2  (parent of node 5)

This representation is cache-friendly (no pointer chasing) and is used by binary heaps precisely because all heap operations traverse parent-child relationships that map to simple index arithmetic.

Choosing a Representation

For most tree algorithms (BST, DFS, LCA) the linked form is cleaner. For heaps and segment trees the array form wins on performance.

Up Next

With the structure in place, the next step is visiting every node systematically. Depth-first traversals give you three distinct orderings — preorder, inorder, and postorder — each useful for different problems.