A comment system stores every reply in an ArrayList. Each row has a parentId. To render a thread you scan for children of the current id, then scan again for their children. A dozen comments feel instant. A few thousand feel like the page is thinking. Nobody “wrote a slow algorithm.” They stored a hierarchy in a layout that can only answer “who reports to this node?” by walking the whole list.
A binary tree is a hierarchical layout: each node has at most a left child and a right child. Left and right are positions, not “up to two kids in a bag.” Parent is optional. The series glossary for ADT vs implementation, Big-O, and worst-case vs amortized lives on the Data Structures Roadmap. This post is the shape itself: node, height vs size, the three words people mix up (full, complete, balanced), and the four walks the layout already owns.
The node is the whole contract
A binary-tree node holds a value and two child pointers. That is the representation. Everything else — height, balance, a traversal — is an operation of that shape.
public class BinaryNode<T> {
T value;
BinaryNode<T> left;
BinaryNode<T> right;
public BinaryNode(T value) {
this.value = value;
}
}left == null and right == null is a leaf. One child set and the other null is a unary node — legal in a binary tree, and the reason a tree of n nodes can look like a linked list. There is no JDK BinaryTree class to import. You either build this node (parsers, expression trees, interview boards) or you sit on a specialized tree (TreeMap, a heap, a trie) whose shape is still this idea with extra rules.
Parent is a fourth pointer you add only when a caller will walk up:
public class BinaryNode<T> {
T value;
BinaryNode<T> left;
BinaryNode<T> right;
BinaryNode<T> parent; // omit unless you walk toward the root
}Downward recursion never reads parent. Upward work — “the sibling of the node I was handed,” bubbling a layout change in a UI tree — does. The extra field is an extra invariant: if n.left is c, then c.parent must be n. Forget that once and every “go up” walk is a lie.
Note: A record is the wrong tool here. Children are wired after construction. Records are for immutable carriers; this node is a mutable layout. Keep it a small class.
Height is not size
Size is how many nodes you allocated. Height is how many edges you walk on the longest root-to-leaf path. They are not synonyms, and that gap is why “a tree of a million nodes” can still be a disaster.
Depth of a node = edges from the root to that node (root depth = 0)
Height of a node = edges on the longest path down to a leaf (leaf height = 0)
Height of a tree = height of the root
Empty tree = height -1 (so a single node has height 0)
Size = number of nodesA stick of four nodes has size 4 and height 3. A bushy tree of four nodes has size 4 and height 1. Same payload, different bill for anything that walks from the root.
int height(BinaryNode<?> n) {
if (n == null) {
return -1; // empty tree
}
return 1 + Math.max(height(n.left), height(n.right));
}
int size(BinaryNode<?> n) {
if (n == null) {
return 0;
}
return 1 + size(n.left) + size(n.right);
}Walk every node and both methods are O(n). The result of height is what later operations pay: search, insert-at-a-leaf-you-must-find, pretty-print by depth. Height sits between about log n and n - 1. The lower end is a bushy tree. The upper end is a linked list wearing left/right fields.
Structure: binary tree (no search-order rule)
size / walk all O(n)
height O(n) to compute; the value is O(log n) .. O(n)
find a value (no order) O(n) — visit until you hit it
link a leaf you already hold O(1) pointer writesThere is no cheap “get by key” on a plain binary tree. That contract is a search tree, a different ADT on the same node shape. This post stops at the shape.
Full, complete, and balanced are three promises
People say “balanced” when they mean “not a stick.” Textbooks use three tighter words. They are definitions, not rotation recipes.
| Word | Promise |
|---|---|
| Full | Every node has 0 or 2 children. No unary nodes. |
| Complete | Every level is filled except possibly the last, and the last is filled left to right. Heap shape. |
| Perfect | Every internal node has two children, and every leaf sits at the same depth. |
| Balanced | For every node, the heights of the two subtrees differ by at most 1. Height is then O(log n). |
A complete tree is always height-balanced. A height-balanced tree is not always complete: the last level may have gaps, as long as no node is lopsided by more than one level. Full forbids the unary node, so the tree cannot be a stick of single children — every internal node branches. Complete pins the fill order. Balanced pins the height gap.
Full: no node has exactly one child
Complete: packed left to right (the array-backed heap picture)
Balanced: |height(left) - height(right)| <= 1 at every nodeBalanced means height stays logarithmic in the size — so a walk from the root does not become a scan of n nodes. It does not mean “we rotate on insert.” Rotations are how some trees keep that promise as you add keys. They are a later article. Here, balanced is a property you can check on a snapshot:
boolean isHeightBalanced(BinaryNode<?> n) {
return balancedHeight(n) != TOO_SKEWED;
}
private static final int TOO_SKEWED = Integer.MIN_VALUE;
int balancedHeight(BinaryNode<?> n) {
if (n == null) {
return -1;
}
int lh = balancedHeight(n.left);
int rh = balancedHeight(n.right);
if (lh == TOO_SKEWED || rh == TOO_SKEWED || Math.abs(lh - rh) > 1) {
return TOO_SKEWED;
}
return 1 + Math.max(lh, rh);
}If you insert already-sorted keys into a tree that also keeps search order, you can grow a stick even though every node still has a left and a right field. The node shape did not save you. The missing promise was balance (or a different layout). Remember the word; do not memorize a rotation on this page.
Traversals are operations of the shape
A traversal is not a puzzle set. It is a way to visit every node once, in an order the pointers already imply. Four of them show up in production code. Same tree, four bills of visit order.
A
/ \
B C
/ \
D EPreorder — node, then left, then right. You process a parent before its children: copy a tree, serialize a prefix, print a file-system path as you descend.
Inorder — left, then node, then right. You finish the left subtree before the node. On a search tree this visit order is sorted; on a plain binary tree it is just “left nest, then me, then right nest.”
Postorder — left, then right, then node. You process children before the parent: free nodes, evaluate an expression tree, compute a folder size from its files.
Level-order — by depth, left to right, with a queue. Breadth-first on a tree: print an org chart by rank, walk a complete tree in heap-array order.
void preorder(BinaryNode<?> n) {
if (n == null) return;
System.out.print(n.value + " ");
preorder(n.left);
preorder(n.right);
}
void inorder(BinaryNode<?> n) {
if (n == null) return;
inorder(n.left);
System.out.print(n.value + " ");
inorder(n.right);
}
void postorder(BinaryNode<?> n) {
if (n == null) return;
postorder(n.left);
postorder(n.right);
System.out.print(n.value + " ");
}
void levelOrder(BinaryNode<?> root) {
if (root == null) return;
Queue<BinaryNode<?>> q = new ArrayDeque<>();
q.add(root);
while (!q.isEmpty()) {
BinaryNode<?> n = q.remove();
System.out.print(n.value + " ");
if (n.left != null) q.add(n.left);
if (n.right != null) q.add(n.right);
}
}On the sketch above those walks print:
preorder A B D E C
inorder D B E A C
postorder D E B C A
level-order A B C D EEach visit is O(n) time and, for the recursive three, O(h) stack. On a stick that stack is O(n) — another reason height is the number that bites. Level-order’s extra memory is the queue, which in a bushy tree peaks around the width of the widest level, not the height.
Pick the walk from the job, not from a problem number. Need the parent before the children? Preorder. Need the children first? Postorder. Need “everyone on this floor, then the next”? Level-order. Need left-nest-then-node? Inorder.
When not to use a binary tree
Skip this layout when the data is not a hierarchy, or when two children is the wrong arity.
- A flat list is enough — tags on a post, a feed, a sequence of events. There is no parent. An
ArrayList(or aHashSetif the job is uniqueness) is the layout. Wrapping each element inBinaryNodedoes not make it a tree; it makes a linked list with an unusedrightfield. - You only scan in insertion order — you never ask “children of X.” A list already answers that.
- A node can have many children — an org chart, a comment thread, a directory with twelve files. That is an n-ary tree (a node plus a list of children), not a binary tree with a clever encoding.
- You needed a map or a heap — production Java almost never allocates
BinaryNodefor “sorted keys” or “next-best element.” Those jobs have layouts (TreeMap,PriorityQueue) whose internals are trees. Reach for the JDK type; do not re-implement the node.
Parent pointers vs not is the same kind of choice:
| You have | You need |
|---|---|
| The root, and you only recurse down | No parent field |
| A node handed in from elsewhere, and you must walk toward the root | parent (or an explicit stack of ancestors) |
| A heap-style complete tree | An array; parent/child are index arithmetic, not pointers |
If you can name the parent from an index ((i - 1) / 2), pointers are ceremony. If you only ever start at the root, parent is a field you will forget to update. Add it when a caller arrives in the middle of the shape and has to go up.
Cheat sheet
Node: value + left + right; parent only if you walk up
Leaf: both children null
Depth: edges from root (root = 0)
Height: longest path down; empty = -1; leaf = 0
Size: node count — not height
Height vs size: h is ~log n (bushy) .. n-1 (stick)
Full: 0 or 2 children
Complete: packed left to right (heap shape)
Balanced: |h(left) - h(right)| <= 1 everywhere → h is O(log n)
Walks: pre (parent first), in (left nest, node, right),
post (children first), level (queue, by depth)
Find (no order): O(n)Do:
- Treat left and right as positions. Null on one side is a real shape, not a missing “second kid.”
- Ask whether height or size is the number in the hot path before you call the tree “small.”
- Pick a traversal from the job: parent-first, children-first, or by level.
- Leave
parentoff until a caller starts in the middle and must go up.
Don’t:
- Store a hierarchy in a list of
parentIdrows and scan for children on every render. - Say “balanced” when you mean “complete,” or “complete” when you mean “not a stick.”
- Recurse on a stick and assume the call stack is
O(log n). - Hand-roll
BinaryNodefor a jobTreeMaporPriorityQueuealready owns.
Wrap-up
A binary tree is a node with two named child slots. Size is how much you stored. Height is how far a root-to-leaf walk runs — logarithmic when the tree is height-balanced, linear when it has degenerated into a stick. Full, complete, and balanced are three different promises: arity, fill order, and height gap. Preorder, inorder, postorder, and level-order are how you visit the pointers you already have, not a contest.
Use this layout when the data is a hierarchy with at most two children per node, or when you are reading a specialized tree whose node is this shape with extra rules. Use a list when there is no parent. Use an n-ary node when a parent can have many children. Terms this series will not re-teach — ADT vs implementation, Big-O, amortized — stay on the Data Structures Roadmap.