Engineering Fluency OS

Why This Matters

Not all data is flat. File systems have folders inside folders. The HTML of a web page is nested elements inside elements. An organization has managers who manage people who manage other people. This kind of hierarchical data is everywhere, and the data structure that represents it is a tree.

Trees are one of the most important structures in computer science. A binary search tree can find a value among millions in about 20 steps. The DOM you manipulate in web development is a tree. Recursion and trees go hand-in-hand — most tree algorithms are elegantly recursive. Understanding trees unlocks a huge category of problems and real-world systems.

Define Terms

Visual Model

8root

The full process at a glance. Click Start tour to walk through each step.

A Binary Search Tree: left children are smaller, right children are larger. Search is O(log n).

Code Example

Code

// Binary Search Tree implementation
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

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

  // Insert a value into the BST
  insert(value) {
    const node = new TreeNode(value);
    if (!this.root) { this.root = node; return; }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) { current.left = node; return; }
        current = current.left;
      } else {
        if (!current.right) { current.right = node; return; }
        current = current.right;
      }
    }
  }

  // Search for a value — O(log n) average
  search(value) {
    let current = this.root;
    while (current) {
      if (value === current.value) return true;
      current = value < current.value ? current.left : current.right;
    }
    return false;
  }

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

const tree = new BST();
[8, 3, 10, 1, 6, 14].forEach(v => tree.insert(v));
console.log(tree.search(6));    // true
console.log(tree.search(7));    // false
console.log(tree.inOrder());    // [1, 3, 6, 8, 10, 14]

Interactive Experiment

Try these exercises:

Insert the values [5, 3, 7, 1, 4, 6, 8] into a BST. Draw the resulting tree on paper.
Run an in-order traversal on your tree. What do you notice about the output order?
What happens if you insert already-sorted values [1, 2, 3, 4, 5]? What shape does the tree take? Why is this a problem?
Try implementing a pre-order traversal (root, left, right) and a post-order traversal (left, right, root). How do the outputs differ?

Quick Quiz

Coding Challenge

Maximum Depth of a Binary Tree

Write a function called `maxDepth` that takes the root node of a binary tree and returns its maximum depth. The depth is the number of nodes along the longest path from the root down to the farthest leaf. An empty tree has depth 0, and a single node has depth 1. Use recursion.

Loading editor...

Real-World Usage

Trees are fundamental to many systems you use every day:

File systems: Directories contain subdirectories and files — a tree structure navigated by your OS
The DOM: HTML documents form a tree of elements. CSS selectors and JavaScript traverse this tree
Databases: B-trees and B+ trees power database indexes, enabling fast queries on billions of rows
Compilers: Abstract Syntax Trees (ASTs) represent the structure of source code during compilation
AI and games: Decision trees and game trees (minimax) power AI decision-making
Autocomplete: Trie trees store dictionaries for fast prefix-based search suggestions

Trees