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 above it.

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

You reach every other node by following edges down from the root. Trees model anything with nested containment: file systems, HTML documents, org charts, and menus. The shape lets you narrow a search quickly, since each step down commits to one branch and drops the rest. That branching is why trees beat flat lists for hierarchical data.

Depth counts edges from the root down to a node; the root has depth zero. Height counts edges on the longest path from a node down to a leaf; 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: search and insert run in time proportional to height.

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. The practical point is that a short height means fast operations. When people say a tree is O(log n), they mean its height stays near log n rather than growing linearly.

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 sounds small but changes how you store and walk the structure. Each node needs just two child pointers, and left versus right becomes meaningful, not just a set of children. 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. Most fast lookup and priority structures build on the binary form for that reason.

Traversal means visiting every node in some defined order. The first three are depth-first and differ only by when you handle the current node relative to its children.

• Pre-order: node first, then left subtree, then right. Good for copying a tree or writing a prefix expression.
• In-order: left, node, right. On a binary search tree this yields sorted values.
• Post-order: left, right, then node. Good for deleting a tree or evaluating results bottom-up.

Level-order is different: it visits nodes row by row from the top down, using a queue. That answers questions about distance from the root, like the shallowest level where something appears.

All four touch every node once, so each costs O(n). The choice is about order, not speed. Pick the one whose visit timing matches what you need to compute.

A binary search tree is a binary tree that keeps its values ordered for fast lookup. The ordering rule is the invariant every node must obey.

For any node, all values in its left subtree are smaller, and all values in its right subtree are larger. This must hold for every node, not just direct children. That last part trips people up: a value deep in the left subtree still must stay below the ancestor it descends from.

This invariant is what makes searching 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 silently 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; if 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.

Inserting reuses the same search path, then attaches the new value where the 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 automatically, since you followed it on the way down.

The cost mirrors search: proportional to height, so O(log n) on a balanced tree and O(n) on a skewed one. Duplicates need a rule decided up front, like sending equals right or bumping a count on the existing node. One catch: inserting already-sorted values builds a long one-sided chain. Without rebalancing, the tree becomes a slow list, which is why real systems self-balance after inserts.

In-order traversal visits the left subtree, then the node, then the right subtree, recursively. Pair that order with the BST invariant and sorted output falls out naturally.

The invariant guarantees everything left of a node is smaller and everything right is larger. So by fully processing the left subtree before touching the node, you emit all smaller values first. Then the node, then all larger values from the right subtree. Apply that reasoning at every level and 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, the invariant is violated somewhere.

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).

The danger is real with ordered input. Inserting sorted values into a plain BST builds a one-sided line, and it silently behaves like a linked list. Self-balancing trees fix this by adjusting shape as you insert and delete, trading a little bookkeeping for a height guarantee. That guarantee is what lets you promise fast lookups regardless of the order data arrives in.

A binary heap is a complete binary tree that maintains a simple ordering between parents and children. Two properties define it together, and both must hold at all times.

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 you store it 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 to each other, so the heap is far weaker than a sorted order. That weakness is the point: it makes reading the top element 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; 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. Want the cheapest task next? Min-heap. Want the highest-scoring item? Max-heap. Peeking the top costs O(1); removing it costs O(log n) either way.

A common trick: if your library only ships one kind, negate the keys to fake the other. That saves writing a second comparator and avoids subtle sign bugs.