Trees and Binary Search Trees Visualized

A tree models a hierarchy: a file system, DOM, syntax tree, or an index-like search structure. Unlike a list, a node may branch into several children. A root has no parent; an edge connects parent and child; siblings share a parent; a leaf has no children. A node's depth counts edges from the root, while a tree's height is its longest root-to-leaf path.

General trees, binary trees, and BSTs

A general tree permits any number of children. A binary tree permits at most two, conventionally left and right. A binary search tree (BST) adds an ordering invariant:

values in the left subtree < node
values in the right subtree > node

That invariant applies recursively at every subtree, not merely to immediate children. Duplicate values require a policy: reject them, store a count, or consistently send equals to one side. There is no universal duplicate rule.

Search and insert follow the invariant

To find 42, compare it to the current node. If smaller, only the left subtree can contain it; if larger, only the right can. Insert repeats the same comparisons until it reaches an empty child.

type Node = { value: number; left?: Node; right?: Node };

function insert(node: Node | undefined, value: number): Node {
  if (!node) return { value };
  if (value < node.value) return { ...node, left: insert(node.left, value) };
  if (value > node.value) return { ...node, right: insert(node.right, value) };
  return node;
}

The implementation copies nodes for clarity. A mutable implementation changes a child reference in place; the invariant is unchanged.

Deletion has three cases

1. A leaf can be removed directly.
2. A node with one child is replaced by that child.
3. A node with two children is commonly replaced with its in-order successor: the smallest node in its right subtree. That successor has no left child, reducing the remaining removal to one of the first two cases.

The visualizer highlights this successor replacement because it is not a swap chosen at random. It preserves the ordering invariant.

Traversals are different questions

• In-order: left, node, right. A BST produces sorted values.
• Pre-order: node, left, right. Useful when recording structure before descendants.
• Post-order: left, right, node. Useful when children must be handled before a parent.
• Level-order: visit by depth, usually with a queue.

Recursive traversals use the call stack. Iterative traversals use an explicit stack, and level-order uses a queue. The data structure reflects the order you need.

Complexity depends on shape

With height $h$, search, insert, and delete take $O(h)$. A suitably balanced tree has $h = O(\log n)$. A degenerate tree formed by inserting already-sorted values has $h = O(n)$, so a BST does not automatically give logarithmic operations. AVL and red-black trees maintain balance through rotations; they are important ideas, but balancing policy is a separate topic.

Real software connections

Trees appear wherever nesting is real: directories, the DOM, expression parsers, and compiler syntax trees. Database indexes are commonly B-trees or related multiway structures rather than ordinary BSTs, because storage pages and disk access change the design constraints. A heap is also tree-shaped but has a different invariant: it only orders parent and child, so it is not a replacement for a BST.

Mistakes and choices

• Checking only a node against its parent misses violations deeper in a subtree.
• Treating in-order traversal as sorted for every binary tree; it is sorted only when the BST invariant holds.
• Assuming a tree is balanced without checking input order or the implementation.
• Use a BST when ordered search and range-style navigation matter; use a hash table for expected average O(1) exact-key lookup; use a heap when only the next priority matters.

Summary

A tree gives structure to relationships. A BST turns comparisons into direction through one invariant, but its speed comes from height, not the name “tree.” Use the visualizer to search, insert, delete, and compare traversal orders while keeping that invariant visible.