Binary Tree

Explanation

A tree is a hierarchical collection of nodes connected by edges, with a single root node at the top. In a binary tree, each node holds a value and has references to at most two children (left and right). Nodes without children are called leaves. The height of a tree is the length of the longest root-to-leaf path. Binary trees come in many variants based on structural properties: a full binary tree has every node with 0 or 2 children (never 1). A complete binary tree fills every level from left to right, leaving no gaps. A perfect binary tree is both full and complete — all leaves at the same level. These structural properties determine whether algorithms are O(log n) or degrade to O(n). The most important variant is the Binary Search Tree (BST): a binary tree where every node in a node's left subtree is less than that node's value, and every node in the right subtree is greater. This ordering property enables O(log n) search, insertion, and deletion in a balanced tree. The critical word is balanced — an unbalanced BST (imagine inserting sorted data: 1, 2, 3, 4, 5) degenerates into a linked list with O(n) operations. Self-balancing BSTs (AVL trees, Red-Black trees) maintain balance automatically. Tree traversal is how you visit all nodes. The three depth-first orderings are: in-order (left, root, right — visits BST nodes in sorted order), pre-order (root, left, right — useful for copying/serializing the tree), and post-order (left, right, root — useful for deletion). Level-order traversal uses a queue to visit nodes level by level.

Code Example

// Binary Search Tree with insert and search
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() { this.root = null; }

  insert(val) {
    const node = new TreeNode(val);
    if (!this.root) { this.root = node; return; }
    let curr = this.root;
    while (true) {
      if (val < curr.val) {
        if (!curr.left) { curr.left = node; return; }
        curr = curr.left;
      } else {
        if (!curr.right) { curr.right = node; return; }
        curr = curr.right;
      }
    }
  }

  // In-order traversal yields sorted output
  inOrder(node = this.root, result = []) {
    if (!node) return result;
    this.inOrder(node.left, result);
    result.push(node.val);
    this.inOrder(node.right, result);
    return result;
  }
}

const tree = new BST();
[5, 3, 7, 1, 4].forEach(v => tree.insert(v));
console.log(tree.inOrder()); // [1, 3, 4, 5, 7]

Why It Matters for Engineers

Trees are everywhere in software: the DOM is a tree of HTML nodes, JSON is a tree structure, file systems are trees of directories and files, compilers parse code into Abstract Syntax Trees (ASTs), and database indexes use B-trees for fast lookups. Understanding binary trees builds the mental model needed to understand all of these. DFS/BFS traversals on trees also generalize to graphs, and many coding interview problems (at companies like Google, Amazon, and Meta) are fundamentally tree traversal problems in disguise. Knowing the three DFS orderings and when to use each is a direct competitive advantage.