Tree Anatomy

The vocabulary page. Every other tree page here, and every problem statement you will ever read, assumes you already know what a root, a leaf, a subtree and a height are, assumes you will not confuse depth with height, and assumes you know why a tree with n nodes always has exactly n - 1 edges. It also assumes you know the shape words - full, complete, perfect, balanced, degenerate - and the arithmetic connecting a tree's height to how many nodes it can hold, because every O(log n) claim about a tree is really a claim about its height. This page is that foundation, drawn out.

It is deliberately about what a tree is. Representation picks up from here with how a tree is stored, and Traversal with how you walk one.

1. What a tree is

A tree is a connected, acyclic graph. Two conditions, and dropping either one gives you something that is not a tree:

• Connected - you can get from any node to any other node.
• Acyclic - there is no way to leave a node and return to it without reusing an edge.

Those two conditions can be traded for counting, which gives four equivalent definitions - use whichever is cheapest to check:

1. connected and acyclic
2. connected with exactly n - 1 edges
3. acyclic with exactly n - 1 edges
4. exactly one path between every pair of nodes

Any two of {connected, acyclic, n - 1 edges} force the third, which is why (2) wins interviews: len(edges) == n - 1 plus a connectivity check is the whole validation, and you never have to hunt for the cycle.

Almost every tree you meet in code is additionally rooted: one node is designated the root, and that single choice orients every edge. Before you pick a root, the tree has no top and no direction - it is just a shape. After, every node except the root has exactly one parent, and words like depth, ancestor and subtree suddenly mean something.

2. The family vocabulary

Rooting the tree turns every edge into a parent-child relationship, and the whole vocabulary is genealogy from there.

Word	Means	On the tree above
Root	The one node with no parent. Every tree has exactly one.	A
Parent	The node one step up. Every node but the root has exactly one - that is what makes it a tree rather than a DAG.	B's parent is A
Child	A node one step down. A node can have any number (binary trees cap it at 2).	A's children are B and C
Sibling	Another child of the same parent.	D and E. E and F are not siblings - different parents.
Ancestor	Any node on the path up to the root, the node itself usually included.	D's ancestors are B and A
Descendant	Anything reachable going down.	B's descendants are D and E
Leaf (external node)	No children at all. Not "one child" - none.	D, E, F
Internal node	Has at least one child. The root counts, unless it is also a leaf.	A, B, C

⚠

A node with one child is not a leaf

A leaf has ZERO children, not "no left child" and not "no right child". This is the single most-made mistake in tree code. if not node.left: leaves += 1 counts every node that is missing a left child, which includes internal nodes leaning right. The correct test is if not node.left and not node.right. The bug survives every symmetric test tree you will hand-write, and dies on the first lopsided one.

3. Depth, height, and level

Three numbers about position, routinely mixed up, all measured on the same tree.

• Depth of a node - the number of edges from the root down to it. The root has depth 0.
• Height of a node - the number of edges on the longest path down to a leaf below it. A leaf has height 0.
• Height of the tree - the height of its root, which is the same as the maximum depth of any node.
• Level - depth plus one, in the convention that calls the root "level 1". Levels are what BFS peels off.

	Depth	Height
Measured from	the root, downward	the leaves, upward
A leaf has	whatever its depth is	0
The root has	0	the height of the whole tree
Computed by	passing a counter down (top-down recursion)	returning a value up (bottom-up recursion)
Single-node tree	0	0
Empty tree	undefined	-1 by convention, so that height(node) = 1 + max(children) keeps working

⚠

Height in edges or in nodes

Half the sources count height in edges and half count it in nodes, so the same tree is "height 2" or "height 3" depending on who is asking. This page, and standard graph theory, count edges: a single node has height 0. But LeetCode 104 ("Maximum Depth of Binary Tree") wants the node count, so its answer for a single node is 1. Neither is wrong. Before writing the base case, decide which one the problem wants: return 0 for empty gives you the node count, return -1 for empty gives you the edge count.

Mnemonic

Depth is how far you have fallen; height is how far you can still fall. Both are measured in the same units on the same tree - they just point in opposite directions. The mnemonic also tells you the recursion shape: depth is an argument you pass down, height is a value you return up.

4. Degree, leaves, and internal nodes

The degree of a node is its number of children. The degree of a tree is the largest degree of any of its nodes - so a binary tree is a tree of degree at most 2.

⚠

Child count is not graph degree

A node's "degree" as a tree and its degree as a graph are different numbers. A non-root internal node of a binary tree has at most 2 children but 3 neighbours (parent plus two children). Tree problems mean the child count; a problem that hands you the tree as an edge list and talks about "adjacent nodes" or "degree" almost always means the graph one. Getting this backwards turns a correct leaf test (degree == 0) into a wrong one - in a free tree, a leaf has graph degree 1, not 0.

5. Subtrees

The subtree rooted at v is v together with every one of its descendants. This is the single most load-bearing idea in tree recursion, because of one property:

A subtree is itself a tree.

That is the whole reason tree code is recursive. solve(node) can call solve(node.left) and treat the answer as finished, because node.left is not "part of a tree" - it is a complete, smaller tree, and the function already handles those.

Two related words that are not the same thing:

• A subtree is a node plus all of its descendants. You do not get to keep some children and drop others.
• A subgraph or an arbitrary connected piece of the tree is not a subtree unless it happens to be closed downward like that. "Subtree of another tree" problems (LeetCode 572) mean the strict version, which is exactly why matching only the shape near the top is a wrong answer.

6. Paths, and why there is exactly one

Between any two nodes of a tree there is exactly one path that does not reuse an edge. Not "at least one" (that is connectivity) and not "possibly several" (that would need a cycle) - exactly one.

That uniqueness is what makes tree problems tractable. On a graph, "the path between u and v" is meaningless without saying which one, and finding the shortest needs a search. On a tree, there is nothing to search for: the path from u to v climbs from u to their lowest common ancestor, then descends to v, and that is the only route there is.

The length of a path is its edge count, and the diameter of a tree is the length of the longest path it contains. Note what the diameter does not have to do: it need not pass through the root. The longest path in a tree can sit entirely inside one subtree, which is exactly the trap in LeetCode 543 and the reason the standard solution returns the height upward while updating a diameter on the side. That pattern is on Traversal and Recursion.

7. Ordered vs unordered trees

In an ordered tree the children of a node have positions, and swapping two of them makes a different tree. In an unordered tree they are just a set.

Binary trees are ordered: node.left and node.right are different fields, so a tree with one left child is not the same tree as one with one right child, even though both are "a root with one child".

As ordered binary trees these are two different trees, and LeetCode 100 (Same Tree) says so. As unordered trees they are the same shape.

This distinction decides real answers. "Is this tree symmetric" (LeetCode 101) is a question about the ordered structure - it compares left.left against right.right. "Are these two n-ary trees the same" often is not, and then you have to sort or canonicalise the children before comparing.

8. The shape names

Four adjectives, routinely swapped for each other. All four describe the same thing: how the missing children are distributed.

The array rows make the point visible: perfect and complete pack with no holes, but full and degenerate leave · gaps in the array even though every value is present in the tree - that wasted space is the array representation breaking down for anything other than a complete shape.

Shape	The rule	Why anyone cares
Full (strictly binary)	Every node has 0 or 2 children. Never exactly one.	Gives you leaves = internal + 1, so counting one side counts the other. Expression trees and Huffman trees are full by construction.
Complete	Every level is full except possibly the last, and the last is filled left to right with no gaps.	This is the shape that packs into an array with no holes. It is the entire reason a heap needs no pointers.
Perfect	Every level, including the last, is completely full.	The best case. n = 2^(h+1) - 1, and exactly half the nodes are leaves.
Balanced	The height is O(log n). The strict per-node version: every node has |height(left) - height(right)| <= 1.	The only property that actually guarantees log n operations. See section 9.
Degenerate (skewed)	Every node has at most one child.	A linked list wearing a tree costume. Height n - 1, every operation O(n), and it is what sorted input builds.

9. Height versus node count: the whole arithmetic

This is the table to memorise. Everything above is a special case of it.

	Minimum	Maximum
Nodes in a tree of height h	h + 1 (a chain)	2^(h+1) - 1 (perfect)
Height of a tree with n nodes	floor(log2(n)) (balanced)	n - 1 (a chain)
Leaves in a tree of height h	1	2^h
Comparisons to reach a leaf	log2(n)	n

Height is the only variable in a tree's cost.

Search, insert, delete, LCA, successor - every one of them is "walk from the root to somewhere," so every one of them costs O(height). O(log n) is not a property of trees. It is a property of short trees, and n nodes fit in log n levels only if you force them to. Everything on Keeping a Tree Balanced exists to force them to.

10. N-ary trees

Lift the two-children cap and you have an n-ary (or k-ary, or general) tree: each node holds a children list of any length.

	Binary tree	N-ary tree
Children	node.left, node.right	node.children, a list
Traversal	two recursive calls	for c in node.children: - one loop
Preorder	unchanged	unchanged
Postorder	unchanged	unchanged
Inorder	root between the two subtrees	undefined - there is no "between" with three children
Height with n nodes, degree k	>= log2(n)	>= log_k(n) - wider means shorter

⚠

Inorder does not exist for n-ary trees

There is no inorder traversal of an n-ary tree. Inorder is defined by the root sitting between the left and right subtree, and a node with three children has two "betweens" and no reason to prefer either. Preorder, postorder and level-order all carry over unchanged. If a problem asks for the "inorder" of an n-ary tree, it is either using the word loosely for preorder or it is a badly worded problem.

Any n-ary tree can be re-encoded as a binary one by the left-child right-sibling transform: binary.left is the first child, binary.right is the next sibling. It is the trick behind representing a general tree with fixed two-pointer nodes, and it is why a "forest" and a "binary tree" are in some sense the same object.

Where to go next

• Representation - TreeNode, the level-order array, parent arrays, and the [1,null,2,3] format problems hand you.
• Traversal and Recursion - the one walk with three visit slots, plus level-order and the recursion patterns that fill them.
• Heaps - the complete-tree array packing from section 9, put to work.
• Keeping a Tree Balanced - what the degenerate case costs and how rotations prevent it.