A binary tree is a set of nodes connected like an upside-down tree. Each node holds a value and points to at most two children: a left child and a right child. One node sits at the very top with no parent — the root — and every other node can be reached from it by following child links downward.
Computer scientists draw trees with the root at the top and the branches growing down. The words come from family trees: a node's children are the nodes directly below it, its parent is the node directly above it, and two nodes with the same parent are siblings. "Binary" just means *at most two* children per node.
The most important idea in this whole course is hidden in the picture above: every child is the root of a smaller tree of its own. Node 2, with 4 and 5 under it, is a complete binary tree by itself — the left subtree of 1. That's why tree problems are solved with recursion: solve it for the two smaller trees, then combine.
Free account
Sign up to read the rest of this lesson: 5 more sections, 3 drawings, a dry-run simulator and code in JavaScript, Python, Java and C++.
Still to come
Was this helpful?
