Trees
Binary Trees Explained
A tree is the first structure where recursion stops being a technique and becomes the natural way to think. A tree is a node with two smaller trees hanging off it - that sentence is the whole subject.
The structure
A node, and a tree
javascript
class TreeNode {
constructor(value, left = null, right = null) {
this.value = value
this.left = left
this.right = right
}
}
// 1
// / \
// 2 3
// / \
// 4 5
const root = new TreeNode(1,
new TreeNode(2, new TreeNode(4), new TreeNode(5)),
new TreeNode(3)
)
console.log(root.value, root.left.value, root.right.value)Root is the top. Leaf is a node with no children. Height is the longest path from root to leaf. A tree is balanced when the two sides differ by at most one level, which is what keeps operations O(log n).
Three depth-first orders
They differ only in when you handle the node relative to its children - one line moving.
Pre, in, and post order
javascript
// From the Binary Trees lesson, repeated so this example runs on its own.
class TreeNode {
constructor(value, left = null, right = null) {
this.value = value
this.left = left
this.right = right
}
}
const root = new TreeNode(1,
new TreeNode(2, new TreeNode(4), new TreeNode(5)),
new TreeNode(3)
)
// Pre-order: node, left, right. Use to copy a tree.
function preOrder(node, out = []) {
if (!node) return out
out.push(node.value)
preOrder(node.left, out)
preOrder(node.right, out)
return out
}
// In-order: left, node, right. On a BST this gives sorted output.
function inOrder(node, out = []) {
if (!node) return out
inOrder(node.left, out)
out.push(node.value)
inOrder(node.right, out)
return out
}
// Post-order: left, right, node. Use to delete, or to size up.
function postOrder(node, out = []) {
if (!node) return out
postOrder(node.left, out)
postOrder(node.right, out)
out.push(node.value)
return out
}
console.log(preOrder(root)) // [1, 2, 4, 5, 3]
console.log(inOrder(root)) // [4, 2, 5, 1, 3]
console.log(postOrder(root)) // [4, 5, 2, 3, 1]Post-order matters more than it looks: it is the only one where you have both children's answers before you handle the node. Anything that combines results from below - height, sums, validity - is post-order.
Level order, breadth first
A queue instead of recursion, walking one level at a time.
Level order
javascript
// From the Binary Trees lesson, repeated so this example runs on its own.
class TreeNode {
constructor(value, left = null, right = null) {
this.value = value
this.left = left
this.right = right
}
}
const root = new TreeNode(1,
new TreeNode(2, new TreeNode(4), new TreeNode(5)),
new TreeNode(3)
)
function levelOrder(root) {
if (!root) return []
const out = []
const queue = [root]
let head = 0
while (head < queue.length) {
const levelSize = queue.length - head
const level = []
for (let i = 0; i < levelSize; i++) {
const node = queue[head++]
level.push(node.value)
if (node.left) queue.push(node.left)
if (node.right) queue.push(node.right)
}
out.push(level)
}
return out
}
console.log(levelOrder(root)) // [[1], [2, 3], [4, 5]]Capturing levelSize before the inner loop is what separates the levels. Without it you get one flat list.
The recursive shape
Nearly every tree question is this:
The template
javascript
function solve(node) {
if (!node) return /* the answer for nothing */
const left = solve(node.left)
const right = solve(node.right)
return /* combine left, right and node.value */
}
function height(node) {
if (!node) return 0
return 1 + Math.max(height(node.left), height(node.right))
}
const demoTree = { value: 1, left: { value: 2, left: null, right: null }, right: null }
console.log(height(demoTree)) // 2Get the base case right and trust the recursion. Do not try to hold the whole tree in your head.
The three depth-first orders
Pre-order, in-order and post-order differ only in when you visit the node relative to its children. Everything else about the recursion is identical, and knowing which one a problem needs is usually the whole solution.
- Pre-order (node, left, right) - copying a tree, serialising it.
- In-order (left, node, right) - on a BST this yields sorted order.
- Post-order (left, right, node) - anything where children must be resolved first: heights, deletion, subtree sums.
All three, plus level order
javascript
function inOrder(node, out = []) {
if (!node) return out
inOrder(node.left, out)
out.push(node.value)
inOrder(node.right, out)
return out
}
// Breadth-first: a queue, not recursion.
function levelOrder(root) {
if (!root) return []
const levels = []
let current = [root]
while (current.length) {
levels.push(current.map((n) => n.value))
const next = []
for (const node of current) {
if (node.left) next.push(node.left)
if (node.right) next.push(node.right)
}
current = next
}
return levels
}
const demoTree = { value: 2, left: { value: 1, left: null, right: null }, right: { value: 3, left: null, right: null } }
console.log(inOrder(demoTree)) // [1, 2, 3]
console.log(levelOrder(demoTree)) // [[2], [1, 3]]Level order is the odd one out - it needs a queue rather than the call stack. Processing one level at a time, as above, is what lets you answer "per level" questions like right-side view or maximum width.
Height and depth are not the same
Depth counts edges down from the root; height counts edges up from the deepest leaf. A problem asking for "the depth of the tree" almost always means the height of the root, and mixing them up produces answers off by one.