Trees and Binary Search Trees

Data That Branches
Tree Vocabulary
A Tree You Already Use
Depth-First Traversal
Breadth-First Traversal
Binary Trees and Binary Search Trees
Searching and Inserting
Deleting a Node
Height and Balance
Interview Problems
Recipe: tree.ts for algolab
Try It Yourself

1. Data That Branches

Arrays, linked lists, stacks, and queues are all lines: one item comes after another. Real data is often not a line. A folder holds folders that hold more folders. A web page has a <body> that holds a <div> that holds a <ul> that holds many <li> items. A company has a CEO, managers under the CEO, and engineers under the managers.

All of these are trees: data that branches downward from a single starting point. Trees are everywhere you look:

the DOM of every web page, which is what React walks when it updates the screen,
the file system on your laptop,
the JSON you get from an API (objects inside objects),
the menu of an online shop (Electronics, then Phones, then Android),
the comment thread under a post, with replies to replies,
the database indexes that make WHERE id = 42 fast, which are usually a kind of tree called a B-tree.

In this chapter you learn the vocabulary, the two ways to walk a tree (depth-first and breadth-first), and then the most useful special case: the binary search tree, which keeps data sorted so you can search it as fast as binary search from the Searching chapter, while still letting you insert and delete.

2. Tree Vocabulary

Here is a small tree. We draw it with the first item at the top, which is how computer scientists always draw trees (upside down compared to real ones).

        A          <- root
       / \
      B   C
     / \   \
    D   E   F      <- D, E, F are leaves

The words to know:

Word	Meaning	In the picture
Node	One item in the tree	`A`, `B`, `C`, ...
Root	The top node, with no parent	`A`
Edge	A link from a parent to a child	`A-B`, `B-D`, ...
Parent	The node directly above	`B` is the parent of `D`
Child	A node directly below	`D` and `E` are children of `B`
Siblings	Nodes with the same parent	`D` and `E`
Leaf	A node with no children	`D`, `E`, `F`
Subtree	A node plus everything below it	`B`, `D`, `E`
Depth	Edges from the root down to a node	`D` has depth 2
Height	Edges from a node down to its deepest leaf	`A` has height 2

Two rules make a tree a tree:

There is exactly one root.
There is exactly one path from the root to any node. No node has two parents, and there are no loops.

If you break rule 2 (a node with two parents, or a link going back up), you no longer have a tree. You have a graph, which is the topic of the next-but-one chapter. A tree is just a graph with strict rules.

A note on counting: we measure depth and height in edges, not nodes. A tree with a single node has height 0. By convention an empty tree has height -1. Some books count nodes instead, so a single node has height 1. Both are fine. Just be clear which one you use. We count edges in this chapter.

3. A Tree You Already Use

Let's turn a folder structure into data. A tree node needs a value and a list of children:

class TreeNode<T> {
  children: TreeNode<T>[] = [];

  constructor(public value: T) {}

  add(value: T): TreeNode<T> {
    const child = new TreeNode(value);
    this.children.push(child);
    return child; // so we can keep adding below the new node
  }
}

const root = new TreeNode("src");
const components = root.add("components");
components.add("Button.tsx");
components.add("Navbar.tsx");
root.add("lib").add("api.ts");
root.add("index.ts");

That builds this folder:

src
├── components
│   ├── Button.tsx
│   └── Navbar.tsx
├── lib
│   └── api.ts
└── index.ts

A node with any number of children is called an n-ary tree (or "general tree"). The DOM is one: an element can hold any number of child elements. The file system is another. In the next sections we walk this folder in different orders.

The public value: T in the constructor is TypeScript shorthand. It declares the property and assigns it in one line, just like writing this.value = value yourself.

4. Depth-First Traversal

Traversing a tree means visiting every node once. There are two families of ways to do it. The first is depth-first search (DFS): go as deep as you can down one branch, then come back and try the next one.

Because a tree is built from smaller trees (every child is the root of its own subtree), DFS is a natural fit for recursion, which you learned in the Recursion chapter. The recipe is: handle this node, then ask each child to do the same.

function preorder<T>(root: TreeNode<T>, visit: (v: T) => void): void {
  visit(root.value);
  for (const child of root.children) preorder(child, visit);
}

const seen: string[] = [];
preorder(root, (v) => seen.push(v));
console.log(seen.join(", "));
// src, components, Button.tsx, Navbar.tsx, lib, api.ts, index.ts

This is preorder: visit the node first, then its children. It is how you would print a folder listing, copy a folder (you must create the parent folder before the files inside it), or serialize a tree to JSON.

Move the visit call after the loop and you get postorder: children first, then the node.

function postorder<T>(root: TreeNode<T>, visit: (v: T) => void): void {
  for (const child of root.children) postorder(child, visit);
  visit(root.value);
}

const done: string[] = [];
postorder(root, (v) => done.push(v));
console.log(done.join(", "));
// Button.tsx, Navbar.tsx, components, api.ts, lib, index.ts, src

Postorder is how you delete a folder (you must empty it before you can remove it) or total up sizes: a folder's size is the sum of its children's sizes, so the children must be done first. Here is that second use, with sizes in kilobytes:

interface Entry {
  name: string;
  size: number; // for a file; folders use 0
}

const files = new TreeNode<Entry>({ name: "src", size: 0 });
const ui = files.add({ name: "components", size: 0 });
ui.add({ name: "Button.tsx", size: 3 });
ui.add({ name: "Navbar.tsx", size: 5 });
files.add({ name: "index.ts", size: 2 });

function totalSize(node: TreeNode<Entry>): number {
  let total = node.value.size;
  for (const child of node.children) total += totalSize(child);
  return total;
}

console.log(totalSize(files)); // 10
console.log(totalSize(ui));    // 8

There are three orders in total for a binary tree (a tree where each node has at most two children, coming up in section 6), and the third is inorder: left subtree, then the node, then the right subtree. We cover it when we meet binary search trees, where it has a very useful property.

The call stack and the cost of recursion matter here. Each recursive call waits on the call stack, so DFS uses memory proportional to the height of the tree. For a balanced tree that is small. For a very tall, skinny tree it can hit a stack overflow, exactly like the deep recursion you saw in the Recursion chapter. You can rewrite DFS with your own stack array instead of recursion when that is a risk.

5. Breadth-First Traversal

The other family is breadth-first search (BFS), also called level order: visit every node at depth 0, then every node at depth 1, then depth 2, and so on. It sweeps across the tree one row at a time.

For this you need a queue from the Stacks and Queues chapter. A queue is first in, first out, so children that are discovered early are visited early. A simple version for our tree keeps one array for the current level and builds the next level from the children:

function levelOrder<T>(root: TreeNode<T>): T[][] {
  const levels: T[][] = [];
  let current: TreeNode<T>[] = [root];

  while (current.length > 0) {
    levels.push(current.map((n) => n.value));
    current = current.flatMap((n) => n.children);
  }
  return levels;
}

console.log(JSON.stringify(levelOrder(root)));
// [["src"],["components","lib","index.ts"],["Button.tsx","Navbar.tsx","api.ts"]]

Each pass of the loop handles one whole level. flatMap gathers all the children of the current level into the next one. The result is an array of levels, which is also exactly what you need to draw the tree row by row, or to answer "what is on the third level?".

Which should you use?

Question	Use
Process children before parents (delete, sum sizes)	DFS postorder
Process parents before children (copy, print, serialize)	DFS preorder
Visit in sorted order (binary search trees)	DFS inorder
Find the closest match to the root	BFS
Row by row, level by level	BFS

Both visit every node exactly once, so both cost O(n) time for n nodes. DFS uses memory up to the height of the tree. BFS uses memory up to the widest level, which for a wide tree can be about half of all nodes. Remember "shortest by number of steps means BFS". It comes back in the Graphs chapter.

6. Binary Trees and Binary Search Trees

A binary tree is a tree where every node has at most two children, called left and right. This small restriction makes the code simpler (two named fields instead of a list) and unlocks a powerful idea.

A binary search tree (BST) is a binary tree with one extra rule that applies at every node:

everything in the left subtree is smaller than the node,
everything in the right subtree is larger than the node.

          50
        /    \
      30      70
     /  \    /  \
    20  40  60  80

Check node 50: the left side has 30, 20, 40, all smaller. The right side has 70, 60, 80, all bigger. Check node 30: left is 20, right is 40. It holds all the way down.

This is the same trick as binary search on a sorted array, built into the shape of the data. At every node you can throw away half the tree. And now we can do the third traversal. Inorder (left, node, right) visits a BST in sorted order:

20, 30, 40, 50, 60, 70, 80

That is the property worth remembering: inorder traversal of a BST gives sorted output. It is also the basis of a classic interview question (section 10).

Here are the node and the class skeleton. We use a compare function so the tree works for numbers, strings, or objects (the same idea as the comparator you passed to Array.sort in the Sorting chapter):

class BSTNode<T> {
  left: BSTNode<T> | null = null;
  right: BSTNode<T> | null = null;

  constructor(public value: T) {}
}

function defaultCompare<T>(a: T, b: T): number {
  return a < b ? -1 : a > b ? 1 : 0;
}

class BinarySearchTree<T> {
  private root: BSTNode<T> | null = null;
  private count = 0;

  constructor(private compare: (a: T, b: T) => number = defaultCompare) {}

  get size(): number {
    return this.count;
  }
}

A null means "no child here". Each method below goes inside the class.

7. Searching and Inserting

Searching follows the rule. Compare the target with the current node. Equal means found. Smaller means go left. Larger means go right. If you fall off the tree (hit null), the value is not there.

has(value: T): boolean {
  let node = this.root;
  while (node !== null) {
    const c = this.compare(value, node.value);
    if (c === 0) return true;
    node = c < 0 ? node.left : node.right;
  }
  return false;
}

Looking for 60 in our tree: 50, bigger, so go right. 70, smaller, so go left. 60, found. Three steps instead of checking all seven values. Looking for 65: 50, right; 70, left; 60, right; that is null. Not found.

Inserting uses the same walk, and puts the new value at the first empty spot where search would have ended up. That keeps the BST rule true without moving any other node.

insert(value: T): boolean {
  if (this.root === null) {
    this.root = new BSTNode(value);
    this.count++;
    return true;
  }

  let node = this.root;
  while (true) {
    const c = this.compare(value, node.value);
    if (c === 0) return false; // already there: no duplicates
    const side = c < 0 ? "left" : "right";
    const next = node[side];
    if (next === null) {
      node[side] = new BSTNode(value);
      this.count++;
      return true;
    }
    node = next;
  }
}

The node[side] trick picks node.left or node.right by name, so we write the "go down or attach" logic once instead of twice. TypeScript is happy because side can only be "left" or "right".

We refuse duplicates and return false, which makes the tree behave like a sorted set. If you need duplicates you can store a count in each node, like the frequency map from the Hash Maps and Sets chapter.

Two small helpers, then the sorted walk and the level walk:

min(): T | undefined {
  if (this.root === null) return undefined;
  return minNode(this.root).value;
}

max(): T | undefined {
  let node = this.root;
  if (node === null) return undefined;
  while (node.right !== null) node = node.right;
  return node.value;
}

inOrder(): T[] {
  const out: T[] = [];
  const walk = (node: BSTNode<T> | null): void => {
    if (node === null) return;
    walk(node.left);
    out.push(node.value);
    walk(node.right);
  };
  walk(this.root);
  return out;
}

The smallest value is found by going left until you cannot, and the largest by going right. With minNode as a plain function outside the class:

function minNode<T>(node: BSTNode<T>): BSTNode<T> {
  while (node.left !== null) node = node.left;
  return node;
}

8. Deleting a Node

Insert and search are easy. Delete is the part of a BST that people dread, but there are only three cases. Find the node, then:

It is a leaf (no children). Just remove it. Replace the link with null.
It has one child. Replace it with that child. The child's whole subtree moves up one level and the rule still holds.
It has two children. You cannot just remove it, because two subtrees are hanging from it. Instead, find the node's in-order successor: the smallest value in its right subtree. Copy that value into this node, then delete the successor from the right subtree. The successor has no left child (it is the smallest), so deleting it is case 1 or case 2.

Why the successor? It is the next value in sorted order. Everything on the left is smaller than it, and everything else on the right is bigger, so it can sit in the deleted node's place without breaking the rule.

Take our tree and delete 30, which has two children (20 and 40):

Before:        50              After:         50
             /    \                         /    \
           30      70                     40      70
          /  \    /  \                   /       /  \
        20   40  60  80                20       60  80

The successor is the smallest value in 30's right subtree, which is 40. We copy 40 into the node and remove the old 40 leaf.

Here is the code. We write it recursively, since each step returns "what should be in this spot now":

delete(value: T): boolean {
  const before = this.count;
  this.root = this.deleteFrom(this.root, value);
  return this.count < before;
}

private deleteFrom(node: BSTNode<T> | null, value: T): BSTNode<T> | null {
  if (node === null) return null; // not found: nothing changes

  const c = this.compare(value, node.value);
  if (c < 0) {
    node.left = this.deleteFrom(node.left, value);
    return node;
  }
  if (c > 0) {
    node.right = this.deleteFrom(node.right, value);
    return node;
  }

  // Found it. Cases 1 and 2: zero or one child.
  if (node.left === null) {
    this.count--;
    return node.right;
  }
  if (node.right === null) {
    this.count--;
    return node.left;
  }

  // Case 3: two children. Copy the successor here, then delete it below.
  const successor = minNode(node.right);
  node.value = successor.value;
  node.right = this.deleteFrom(node.right, successor.value);
  return node;
}

Read it as: "delete from the left, or from the right, and keep whatever comes back". When the node is found, a leaf returns node.right, which is null, so it disappears. A node with only a right child returns that child, and with only a left child returns that child. Only the two-child case does the copy trick, and the recursive call at the end is the one that decrements count.

9. Height and Balance

How fast are search, insert, and delete? Each walks one path from the root down, so the cost is the height of the tree, h. Here is a way to compute it:

height(): number {
  const h = (node: BSTNode<T> | null): number =>
    node === null ? -1 : 1 + Math.max(h(node.left), h(node.right));
  return h(this.root);
}

The height of an empty tree is -1, a leaf is 1 + max(-1, -1) = 0, and everything else is one more than its taller child. Remember postorder: the children are computed first.

Now the important question: how large is h? It depends on the shape of the tree, and the shape depends on the order you inserted the data.

Insert 50, 30, 70, 20, 40, 60, 80 and you get the nicely spread tree from before, with height 2 for 7 nodes. Now insert 1, 2, 3, 4, 5, 6, 7 in order:

1
 \
  2
   \
    3
     \
      4  ...and so on down to 7

Every new value is bigger than everything so far, so it always goes to the right. The BST has turned into a linked list, with height 6 for 7 nodes. Searching it is a linear scan. Sorted data (or reverse-sorted data) is the worst input for a plain BST, and sorted data is very common in real life.

Tree shape	Height for `n` nodes	Search / insert / delete
Balanced (spread evenly)	about `log₂ n`	O(log n)
Skewed (a line)	`n - 1`	O(n)

For 1,000,000 values, a balanced tree has a height of about 19, so any lookup checks at most about 20 nodes. A skewed tree with the same values could take a million steps. The difference is enormous, which is why a balanced tree matters.

This is why production code almost never uses a plain BST. It uses a self-balancing tree, which rearranges itself with small moves called rotations after each insert or delete, so the height stays near log₂ n no matter what order the data arrives in. The best-known are AVL trees and red-black trees (used inside the standard libraries of Java and C++ for sorted maps). Databases use a close cousin, the B-tree, which has many children per node to read fewer pages from disk.

You do not need to implement rotations for most interviews. You do need to say, in one sentence, why a plain BST can degrade to O(n) and what fixes it. You can also keep a plain BST healthy by inserting the data in a shuffled order, because random order tends to give a roughly balanced tree.

Compare the BST against the structures you already know:

Structure	Search	Insert	Delete	Sorted order?
Unsorted array	O(n)	O(1) at the end	O(n)	No
Sorted array	O(log n)	O(n)	O(n)	Yes
Hash map / set	O(1) average	O(1) average	O(1) average	No
BST, balanced	O(log n)	O(log n)	O(log n)	Yes
BST, skewed	O(n)	O(n)	O(n)	Yes

A hash map is faster for plain lookups, so why use a BST? Because a BST keeps the data in order. It can answer "what is the smallest value?", "what comes right after 45?", and "give me everything between 30 and 60" without scanning or sorting. A hash map cannot.

10. Interview Problems

Tree questions are among the most common in interviews. Almost all of them are the same recursive pattern: solve it for the left subtree, solve it for the right subtree, then combine the two answers at this node. These examples use a minimal node shape so you can write them on a whiteboard:

interface BinaryNode {
  value: number;
  left: BinaryNode | null;
  right: BinaryNode | null;
}

const node = (
  value: number,
  left: BinaryNode | null = null,
  right: BinaryNode | null = null,
): BinaryNode => ({ value, left, right });

Validate a BST. Given a tree, is it a valid BST? A common wrong answer only checks that each node is bigger than its left child and smaller than its right child. That misses a deep node that breaks a rule set far above. The correct answer passes down the allowed range:

function isValidBST(
  root: BinaryNode | null,
  low = -Infinity,
  high = Infinity,
): boolean {
  if (root === null) return true;
  if (root.value <= low || root.value >= high) return false;
  return (
    isValidBST(root.left, low, root.value) &&
    isValidBST(root.right, root.value, high)
  );
}

const good = node(50, node(30, node(20), node(40)), node(70));
const bad = node(50, node(30, node(20), node(60)), node(70));

console.log(isValidBST(good)); // true
console.log(isValidBST(bad));  // false  (60 is in the left subtree of 50)

In bad, the 60 is a fine right child of 30, but it sits in the left subtree of 50 and is bigger than 50. Going left from 50 sets the upper limit to 50, so 60 fails. The other approach is to run inorder and check that the output is strictly increasing. Both are O(n).

Invert a binary tree. Swap left and right at every node. It sounds tricky, but it is only a few lines:

function invert(root: BinaryNode | null): BinaryNode | null {
  if (root === null) return null;
  const left = invert(root.left);
  const right = invert(root.right);
  root.left = right;
  root.right = left;
  return root;
}

For 2 with children 1 and 3, the inorder output goes from 1, 2, 3 to 3, 2, 1.

Lowest common ancestor in a BST. Given two values, find the lowest node that has both of them below it (or is one of them). In a BST you never need to search both sides. If both values are smaller than the current node, go left. If both are bigger, go right. Otherwise the paths split here, so this is the answer:

function lowestCommonAncestor(root: BinaryNode, p: number, q: number): number {
  let current = root;
  while (true) {
    if (p < current.value && q < current.value) current = current.left!;
    else if (p > current.value && q > current.value) current = current.right!;
    else return current.value;
  }
}

const tree = node(
  50,
  node(30, node(20), node(40)),
  node(70, node(60), node(80)),
);

console.log(lowestCommonAncestor(tree, 20, 40)); // 30
console.log(lowestCommonAncestor(tree, 20, 60)); // 50
console.log(lowestCommonAncestor(tree, 30, 40)); // 30  (a node can be its own ancestor)

This runs in O(h) time and O(1) memory. The ! tells TypeScript "trust me, this is not null". It is safe here because we assume both values exist in the tree.

Right side view. If you stood to the right of the tree, which nodes would you see? It is the last node of each level, so it is level-order traversal with a small twist:

function rightSideView(root: BinaryNode | null): number[] {
  if (root === null) return [];
  const view: number[] = [];
  let level = [root];

  while (level.length > 0) {
    view.push(level[level.length - 1].value);
    level = level.flatMap((n) =>
      [n.left, n.right].filter((c): c is BinaryNode => c !== null),
    );
  }
  return view;
}

console.log(rightSideView(tree)); // [ 50, 70, 80 ]

The filter with c is BinaryNode is a TypeScript type guard. It removes the null entries and tells the compiler that what is left is all real nodes.

Iterative inorder. Interviewers often follow up with "now do it without recursion". Use your own stack:

function inOrderIterative(root: BinaryNode | null): number[] {
  const out: number[] = [];
  const stack: BinaryNode[] = [];
  let current = root;

  while (current !== null || stack.length > 0) {
    while (current !== null) {
      stack.push(current); // remember the way back
      current = current.left;
    }
    const top = stack.pop()!;
    out.push(top.value);
    current = top.right;
  }
  return out;
}

It goes as far left as possible, pushing nodes as it goes, then pops one (visit it), then moves to that node's right child and repeats. The stack array plays the role the call stack played in the recursive version.

11. Recipe: tree.ts for algolab

Create src/bst.ts in algolab with the n-ary tree helpers and the binary search tree from this chapter:

// ---------- A general tree (DOM, folders, menus) ----------

export class TreeNode<T> {
  children: TreeNode<T>[] = [];

  constructor(public value: T) {}

  add(value: T): TreeNode<T> {
    const child = new TreeNode(value);
    this.children.push(child);
    return child;
  }
}

export function preorder<T>(root: TreeNode<T>, visit: (v: T) => void): void {
  visit(root.value);
  for (const child of root.children) preorder(child, visit);
}

export function postorder<T>(root: TreeNode<T>, visit: (v: T) => void): void {
  for (const child of root.children) postorder(child, visit);
  visit(root.value);
}

export function levelOrder<T>(root: TreeNode<T>): T[][] {
  const levels: T[][] = [];
  let current: TreeNode<T>[] = [root];
  while (current.length > 0) {
    levels.push(current.map((n) => n.value));
    current = current.flatMap((n) => n.children);
  }
  return levels;
}

export function treeHeight<T>(root: TreeNode<T> | null): number {
  if (root === null) return -1;
  let tallest = -1;
  for (const child of root.children) {
    tallest = Math.max(tallest, treeHeight(child));
  }
  return tallest + 1;
}

// ---------- A binary search tree ----------

class BSTNode<T> {
  left: BSTNode<T> | null = null;
  right: BSTNode<T> | null = null;
  constructor(public value: T) {}
}

export class BinarySearchTree<T> {
  private root: BSTNode<T> | null = null;
  private count = 0;

  constructor(private compare: (a: T, b: T) => number = defaultCompare) {}

  get size(): number {
    return this.count;
  }

  insert(value: T): boolean {
    if (this.root === null) {
      this.root = new BSTNode(value);
      this.count++;
      return true;
    }
    let node = this.root;
    while (true) {
      const c = this.compare(value, node.value);
      if (c === 0) return false;
      const side = c < 0 ? "left" : "right";
      const next = node[side];
      if (next === null) {
        node[side] = new BSTNode(value);
        this.count++;
        return true;
      }
      node = next;
    }
  }

  has(value: T): boolean {
    let node = this.root;
    while (node !== null) {
      const c = this.compare(value, node.value);
      if (c === 0) return true;
      node = c < 0 ? node.left : node.right;
    }
    return false;
  }

  min(): T | undefined {
    if (this.root === null) return undefined;
    return minNode(this.root).value;
  }

  max(): T | undefined {
    let node = this.root;
    if (node === null) return undefined;
    while (node.right !== null) node = node.right;
    return node.value;
  }

  delete(value: T): boolean {
    const before = this.count;
    this.root = this.deleteFrom(this.root, value);
    return this.count < before;
  }

  private deleteFrom(node: BSTNode<T> | null, value: T): BSTNode<T> | null {
    if (node === null) return null;
    const c = this.compare(value, node.value);
    if (c < 0) {
      node.left = this.deleteFrom(node.left, value);
      return node;
    }
    if (c > 0) {
      node.right = this.deleteFrom(node.right, value);
      return node;
    }
    if (node.left === null) {
      this.count--;
      return node.right;
    }
    if (node.right === null) {
      this.count--;
      return node.left;
    }
    // Two children: copy the in-order successor here, then delete it below.
    const successor = minNode(node.right);
    node.value = successor.value;
    node.right = this.deleteFrom(node.right, successor.value);
    return node;
  }

  inOrder(): T[] {
    const out: T[] = [];
    const walk = (node: BSTNode<T> | null): void => {
      if (node === null) return;
      walk(node.left);
      out.push(node.value);
      walk(node.right);
    };
    walk(this.root);
    return out;
  }

  levelOrder(): T[][] {
    const levels: T[][] = [];
    let current: BSTNode<T>[] = this.root === null ? [] : [this.root];
    while (current.length > 0) {
      levels.push(current.map((n) => n.value));
      const next: BSTNode<T>[] = [];
      for (const n of current) {
        if (n.left !== null) next.push(n.left);
        if (n.right !== null) next.push(n.right);
      }
      current = next;
    }
    return levels;
  }

  height(): number {
    const h = (node: BSTNode<T> | null): number =>
      node === null ? -1 : 1 + Math.max(h(node.left), h(node.right));
    return h(this.root);
  }
}

function minNode<T>(node: BSTNode<T>): BSTNode<T> {
  while (node.left !== null) node = node.left;
  return node;
}

function defaultCompare<T>(a: T, b: T): number {
  return a < b ? -1 : a > b ? 1 : 0;
}

Now the tests. Create src/bst.test.ts:

import { test } from "node:test";
import assert from "node:assert/strict";
import {
  TreeNode,
  preorder,
  postorder,
  levelOrder,
  treeHeight,
  BinarySearchTree,
} from "./bst.ts";

function sample(): TreeNode<string> {
  const root = new TreeNode("src");
  const components = root.add("components");
  components.add("Button.tsx");
  components.add("Navbar.tsx");
  root.add("lib").add("api.ts");
  root.add("index.ts");
  return root;
}

test("preorder visits a parent before its children", () => {
  const seen: string[] = [];
  preorder(sample(), (v) => seen.push(v));
  assert.deepEqual(seen, [
    "src", "components", "Button.tsx", "Navbar.tsx", "lib", "api.ts", "index.ts",
  ]);
});

test("postorder visits children before the parent", () => {
  const seen: string[] = [];
  postorder(sample(), (v) => seen.push(v));
  assert.deepEqual(seen, [
    "Button.tsx", "Navbar.tsx", "components", "api.ts", "lib", "index.ts", "src",
  ]);
});

test("levelOrder groups by depth, and height counts edges", () => {
  assert.deepEqual(levelOrder(sample()), [
    ["src"],
    ["components", "lib", "index.ts"],
    ["Button.tsx", "Navbar.tsx", "api.ts"],
  ]);
  assert.equal(treeHeight(sample()), 2);
  assert.equal(treeHeight(null), -1);
});

test("BST keeps values sorted and ignores duplicates", () => {
  const bst = new BinarySearchTree<number>();
  for (const n of [50, 30, 70, 20, 40, 60, 80]) bst.insert(n);
  assert.deepEqual(bst.inOrder(), [20, 30, 40, 50, 60, 70, 80]);
  assert.equal(bst.insert(60), false);
  assert.equal(bst.size, 7);
  assert.equal(bst.has(60), true);
  assert.equal(bst.has(65), false);
  assert.equal(bst.min(), 20);
  assert.equal(bst.max(), 80);
  assert.equal(bst.height(), 2);
});

test("BST delete handles leaf, one child, and two children", () => {
  const bst = new BinarySearchTree<number>();
  for (const n of [50, 30, 70, 20, 40, 60, 80]) bst.insert(n);
  assert.equal(bst.delete(20), true); // leaf
  assert.equal(bst.delete(30), true); // now has one child (40)
  assert.equal(bst.delete(50), true); // two children (root)
  assert.equal(bst.delete(99), false); // not there
  assert.deepEqual(bst.levelOrder(), [[60], [40, 70], [80]]);
  assert.equal(bst.size, 4);
});

test("sorted input makes a lopsided tree", () => {
  const bst = new BinarySearchTree<number>();
  for (let i = 1; i <= 7; i++) bst.insert(i);
  assert.equal(bst.height(), 6);
});

Run the tests:

npx tsx --test

You should see all six tests pass. Look at the delete test: it removes a leaf (20), then a node that now has a single child (30, after 20 is gone), then the root with two children (50). The last test proves the warning from section 9, with a height of 6 for just 7 values.

Add the export to src/index.ts:

export * from "./bst.ts";

Then create demo-trees.ts in the project root:

import {
  BinarySearchTree,
  TreeNode,
  levelOrder,
  preorder,
  postorder,
} from "./src/bst.ts";

const bst = new BinarySearchTree<number>();
for (const n of [50, 30, 70, 20, 40, 60, 80]) bst.insert(n);

console.log("sorted:", bst.inOrder().join(" "));
console.log("levels:", JSON.stringify(bst.levelOrder()));
console.log("height:", bst.height());
console.log("has 60:", bst.has(60), "| has 65:", bst.has(65));

bst.delete(30);
console.log("after delete 30:", JSON.stringify(bst.levelOrder()));

const root = new TreeNode("src");
root.add("components").add("Button.tsx");
root.add("index.ts");

const before: string[] = [];
const after: string[] = [];
preorder(root, (v) => before.push(v));
postorder(root, (v) => after.push(v));
console.log("preorder:", before.join(", "));
console.log("postorder:", after.join(", "));
console.log("levels:", JSON.stringify(levelOrder(root)));

Run it:

npx tsx demo-trees.ts

sorted: 20 30 40 50 60 70 80
levels: [[50],[30,70],[20,40,60,80]]
height: 2
has 60: true | has 65: false
after delete 30: [[50],[40,70],[20,60,80]]
preorder: src, components, Button.tsx, index.ts
postorder: Button.tsx, components, index.ts, src
levels: [["src"],["components","index.ts"],["Button.tsx"]]

After deleting 30, the tree has 40 where 30 used to be. That is the in-order successor trick from section 8, with 20 still hanging on the left.

12. Try It Yourself

Draw and walk. Draw the BST you get from inserting 8, 3, 10, 1, 6, 14, 4, 7, 13 in that order. Write its preorder, inorder, postorder, and level-order lists by hand, then check them in code. What is its height?
Count and sum. Add count(root) (the number of nodes) and sumValues(root) (for a TreeNode<number>). Both are postorder in spirit. What does count return for a single node?
Find the maximum depth. Write maxDepth(root: BinaryNode | null) that returns the number of nodes on the longest path from the root down to a leaf. How is it different from height() in this chapter?
Skew it. Insert 1 to 1000 in order into a BinarySearchTree, and time 1000 calls to has(1000). Now insert the same numbers in a shuffled order and time again (shuffle with the Fisher-Yates idea from the Math for Programmers Probability chapter). How different are the heights?
Interview: kth smallest. Given a BST and a number k, return the k-th smallest value. Hint: inorder gives sorted order, so stop after k visits. Can you do it without collecting the whole sorted array?
Interview: same tree? Write isSameTree(a, b) that returns true when two binary trees have the same shape and the same values. Compare the nodes, then the left subtrees, then the right subtrees.
Interview: serialize. Write serialize(root) that turns a binary tree into a string such as "1,2,#,#,3,#,#" using preorder, with # for null, and deserialize(text) that rebuilds it. Why do you need the # markers?

A tree is a way to store data that branches, and a binary search tree is a way to keep it sorted. Next comes a tree with a different rule, where the smallest item must always sit at the top so that you can grab it at once. In Heaps and Priority Queues we build one on top of a plain array, and use it to find the top K items in a list and to schedule tasks by priority.