Introduction to Tree

What a Tree Actually Is

A tree is a set of nodes connected by directed parent→child edges such that exactly one node (the root) has no parent, and every other node has exactly one parent reachable from the root by a unique path. That single constraint — one path from root to any node, no cycles, no node with two parents — is what makes a tree a restricted, acyclic connected graph rather than a general graph: it guarantees recursive self-similarity (every node's descendants form a smaller tree, a subtree), which is why almost every tree algorithm is written as "solve it at this node using the answers already solved for its children."

Recognize the pattern

• Data is naturally hierarchical: one parent, many possible children (file systems, org charts, DOM, category trees, decision paths).
• You need fast search/insert with an ordering property (binary search trees), or you need to answer aggregate questions bottom-up (height, sum, LCA).
• The problem statement says "parent", "ancestor", "subtree", "level", or gives you a node with left/right/children pointers.
• A stack/queue-based traversal (DFS/BFS) is the natural way to visit every element exactly once.

Terminology (precise, not just vibes)

Brute force vs. the tree's optimal shape

If you stored the same hierarchical data in a flat array and needed "find all descendants of X" or "is A an ancestor of B", you would linearly scan and reconstruct relationships every time — O(n) per query with extra bookkeeping. A tree makes ancestry structural: descendants are just "everything reachable by following child pointers", so a single DFS from X answers it in O(size of X's subtree), and parent/child lookup is O(1) via pointers instead of O(n) search through a flat structure.

Complexity, derived

For a tree with n nodes and height h: a full traversal (DFS or BFS) visits each node once and follows each edge once → exactly n node-visits and n−1 edge-traversals, giving O(n) time. Space is O(h) for DFS (the recursion/call stack holds at most one frame per level on the current root-to-leaf path) and O(w) for BFS where w is the tree's maximum width (the queue holds one full level at a time).

The height-vs-n relationship depends on exactly what "balanced" means, and the geometric-sum argument below applies only to a complete (or full) binary tree, where level i holds up to 2ⁱ nodes: summing levels 0..h gives n ≤ 2h+1−1, so h = ⌊log₂ n⌋ exactly. Real-world "balanced" self-balancing BSTs only guarantee this order of growth, not the exact formula — an AVL tree's height is at most ≈1.44 log₂ n, and a red-black tree's is at most 2 log₂(n+1). The correct general statement is: a balanced tree has height h = Θ(log n); only a complete/full binary tree pins that down to the exact floor(log₂ n). For a degenerate tree (every node has one child, i.e. a linked list in disguise), h = n−1 — this is exactly why unbalanced BSTs degrade to O(n) search instead of O(log n).

Worked example: compute height by hand

Tree: A(root) → B, C  |  B → D, E  |  C → F.

Tree height = 2. This is the recurrence height(node) = -1 if node is null else 1 + max(height(left), height(right)), evaluated bottom-up — the canonical example of solving a tree problem via post-order recursion.

Java: node definition and the height recurrence

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

int height(TreeNode node) {
    if (node == null) return -1;          // convention: empty subtree has height -1
    return 1 + Math.max(height(node.left), height(node.right));
}

// Locates a specific node OBJECT, not a value. Uses reference equality
// (==) on purpose: root == target only matches if target is the exact
// node instance from this tree, not a different node that happens to
// hold an equal .val. If you need "find the node whose value equals X",
// compare root.val == target.val instead — that is a different,
// value-based search with different duplicate-handling semantics.
int depth(TreeNode root, TreeNode target, int d) {
    if (root == null) return -1;
    if (root == target) return d;
    int left = depth(root.left, target, d + 1);
    if (left != -1) return left;
    return depth(root.right, target, d + 1);
}

Pitfalls

• Off-by-one on height vs. depth. Some definitions count nodes on the path, others count edges (used here). A single leaf tree has height 0 by the edge convention, not 1 — mixing conventions silently breaks base cases.
• Confusing "complete" with "full". A complete tree can have a node with only one child (the last one on the bottom level); a full tree never can. Heap array-indexing (2i+1, 2i+2) relies on completeness, not fullness.
• Treating "balanced" as "complete". The clean h = floor(log₂ n) formula only holds for complete/full binary trees. AVL and red-black trees are balanced but not complete, so only claim h = Θ(log n) for them — using the exact formula overstates precision you don't have.
• Recursion depth = tree height. An unbalanced tree (e.g., nodes inserted in sorted order into a BST) has height O(n), so recursive traversal can stack-overflow on large skewed inputs — iterative traversal with an explicit stack avoids this.
• Forgetting a node is its own ancestor/descendant in some problem definitions (e.g., LCA) but not others — always check the problem's convention before coding.

When to use a tree / when not, and vs. alternatives

• Use a tree when data is genuinely hierarchical and you need O(log n) search/insert with ordering (BST family), or need to represent nested structure (parse trees, file systems, DOM).
• Use a plain array/list instead when there's no hierarchy and you only need sequential access — a tree adds pointer overhead and cache-unfriendly traversal for no benefit.
• Use a hash map instead when you only need O(1) key→value lookup with no need for ordering, range queries, or ancestry — a tree pays O(log n) for guarantees you don't need.
• Use a general graph instead when relationships aren't strictly one-parent-per-node (e.g., a node can have multiple "parents", or cycles are possible) — forcing that into a tree loses information.

Takeaways

• A tree is a connected acyclic graph with a single root and unique root-to-node paths — that uniqueness is what enables recursive, subtree-based algorithms.
• Height and depth are edge-counts measured in opposite directions (depth from root down, height from node down to its deepest leaf); tree height = root's height.
• Traversal cost is always O(n) time; the space cost (O(h) for DFS vs O(w) for BFS) is what actually differs and matters for skewed vs. balanced trees.
• The exact h = floor(log₂ n) bound is only valid for complete/full binary trees; general balanced trees (AVL, red-black) only guarantee h = Θ(log n). A degenerate (linked-list-shaped) tree gives h = n−1, i.e. O(n) — balance is the whole game in later BST/heap topics.

Recall: Why is DFS's space complexity O(height) rather than O(number of nodes), and what real-world input shape makes that bound approach O(n)?

Compiled from standard tree terminology (root, height, depth, full/complete binary trees) as used in CLRS-style treatments and common interview-prep references; height recurrence and complexity derivation are original to this page.