Trees, BSTs & Heaps.

A tree is a hierarchical structure of nodes connected by edges, with no cycles. Each node holds a value and links to nodes below it. One node sits at the top as the root, the single entry point with no parent.

Parent and child describe a direct link. The node above is the parent, and the nodes hanging off it are its children. A leaf is any node with no children. Internal nodes have at least one child.

You reach every other node by following edges down from the root. Trees model nested containment, such as file systems, HTML documents and org charts. Each step down a search commits to one branch and drops the rest, which is why trees beat flat lists for hierarchical data.

Depth counts edges from the root down to a node, so the root has depth zero. Height counts edges on the longest path from a node down to a leaf, so a leaf has height zero.

So depth looks upward toward the root, and height looks downward toward the deepest descendant. The whole tree's height equals the root's height, which is the longest root-to-leaf path. That number drives cost, because search and insert run in time proportional to height.

A short height means fast operations. When people say a tree is O(log n), they mean its height stays near log n instead of growing linearly.

A common mix-up is swapping the two or counting nodes instead of edges. Some texts count nodes, making both values larger by one, so always confirm the convention.

A binary tree limits each node to at most two children, usually named left and right. A general tree lets a node have any number of children, with no fixed slots.

That cap changes how you store and walk the structure. Each node needs just two child pointers, and left versus right becomes meaningful. This ordering is what later lets binary search trees and heaps assign meaning to sides.

An empty spot matters too. A node can have a left child but no right, and that gap is part of the shape.

General trees suit data with variable fan-out, like a folder holding any number of files. Binary trees suit ordered decisions, where each step picks one of two directions, and most fast lookup and priority structures build on that form.

They are four ways to visit every node of a tree in a defined order. The first three are depth-first and differ only by when you handle the current node relative to its children.

• Pre-order visits the node, then the left subtree, then the right. It suits copying a tree or writing a prefix expression.
• In-order visits left, node, right, which yields sorted values on a binary search tree.
• Post-order visits left, right, then the node. It suits deleting a tree or evaluating results bottom-up.

Level-order is the breadth-first one, visiting nodes row by row from the top with a queue. It suits questions about distance from the root.

All four touch every node once, so each costs O(n). The choice is about order, not speed.

A binary search tree is a binary tree that keeps its values ordered for fast lookup. Its invariant is that for any node, all values in its left subtree are smaller and all values in its right subtree are larger.

The rule covers whole subtrees, not just direct children, so a value deep in the left subtree must stay below the ancestor it descends from.

The invariant makes search cheap. At each node you compare, then discard a whole subtree and follow the other side. Duplicates need a chosen policy, such as always going right or storing a count. Keep the invariant true on every insert and delete, and lookups stay logarithmic on a balanced tree. Break it anywhere and searches can miss values that are present.

Searching starts at the root and compares your target to the current node. If they match, you are done. If the target is smaller, go left, and if it is larger, go right. Repeat until you find it or fall off the tree into an empty spot, which means absent.

Each step throws away one subtree, so you follow a single root-to-leaf path. That means the cost is proportional to the tree's height, not its node count.

while (node && node.val !== target)
  node = target < node.val ? node.left : node.right;
// node is the match or null

On a balanced tree the height is about log n, so search runs in O(log n). On a lopsided tree that degrades toward O(n), since the path can be as long as the node count. That gap is exactly why balancing matters.

Insertion follows the path a search for the value would take, then attaches the new value where that search would have failed. You walk down comparing, going left for smaller and right for larger, until you reach an empty child slot. You place the new node there as a leaf.

New values always land as leaves, so existing nodes never move. That keeps insertion simple and preserves the ordering invariant, since you followed it on the way down.

Duplicates need a rule decided up front, like sending equals right or bumping a count on the existing node.

The cost mirrors search. It is proportional to height, so O(log n) on a balanced tree and O(n) on a skewed one. Sorted input builds a long one-sided chain that every operation walks like a linked list, which is why real systems self-balance after inserts.

In-order traversal visits the left subtree, then the node, then the right subtree, and the BST invariant puts those three parts in ascending order. Everything in a node's left subtree is smaller than the node, and everything in its right subtree is larger. So the traversal emits all smaller values before the node and all larger values after it. The same holds at every level, so the whole sequence comes out ascending.

inorder(node.left);
visit(node.val);
inorder(node.right);
// prints values low to high

This gives you a free sorted listing in O(n) without any extra sorting step. It also means you can spot a broken tree cheaply. If an in-order pass ever emits a value smaller than the previous one, some node violates the invariant.

Balanced means the tree's height stays close to the minimum for its node count, roughly log n. No branch is allowed to grow much longer than the others. Different schemes define the slack differently, but all cap how lopsided the shape can get.

Height matters because search, insert and delete all cost time proportional to it. A balanced tree keeps those at O(log n). An unbalanced one can stretch into a chain, dragging the same operations toward O(n).

Ordered input makes this real. Inserting sorted values into a plain BST builds a one-sided line that behaves like a linked list. Self-balancing trees adjust their shape as you insert and delete, trading a little bookkeeping for a height guarantee. That guarantee keeps lookups fast whatever order the data arrives in.

A binary heap is a complete binary tree with a simple ordering between parents and children. Two properties define it, and both must always hold.

The shape property says the tree is complete. Every level is full except possibly the last, which fills left to right. That compact shape lets it live in a plain array with no pointers.

The heap property is a parent-child rule. In a max-heap, every parent is at least as large as its children, so the largest value sits at the root. A min-heap flips it, keeping the smallest at the root. The rule only relates parents to their own children, not siblings, so a heap is far weaker than a sorted order. That weakness makes reading the top O(1) while keeping inserts cheap.

The only difference is which extreme sits at the root. A min-heap keeps its smallest value on top, and a max-heap keeps its largest. Both obey the same shape rule and the same parent-child ordering, just flipped.

In a min-heap, every parent is smaller than or equal to its children. In a max-heap, every parent is larger than or equal to its children. Neither orders siblings, so you cannot read a sorted list off the array.

You pick based on what you pull first. To take the cheapest task next, use a min-heap. To take the highest-scoring item, use a max-heap. Peeking at the top costs O(1), and removing it costs O(log n) either way.

If your library only ships one kind, negating numeric keys fakes the other.