🌳 Analogy
A binary tree is a family tree where everyone has at most two children. Start from the single ancestor at the top (the root) and you can always reach anyone by going left or right at each person. There are no cousins marrying back in — every node has exactly one parent, so there are no cycles and no shortcuts.
A node with two children
Each node holds a value and two pointers, Left and Right, either of which may be nil. The tree is identified by its root:
graph TD A["1 (root)"] --> B["2"] A --> C["3"] B --> D["4"] B --> E["5"] C --> F["6"]
type Node struct {
Val int
Left *Node
Right *Node
}A node with no children is a leaf. The depth of a node is the number of edges from the root down to it (the root has depth 0). The height of the tree is the depth of its deepest leaf — the length of the longest root-to-leaf path. A balanced tree of n nodes has height about log₂ n; a degenerate tree that chains to one side has height n − 1, behaving like a linked list.
Three depth-first traversals
Depth-first traversal recurses all the way down one branch before backing up. The only thing that differs between the three classic orders is when you visit the node relative to its subtrees:
- Inorder — left subtree, node, right subtree.
- Preorder — node, left subtree, right subtree.
- Postorder — left subtree, right subtree, node.
package main
import "fmt"
type Node struct {
Val int
Left *Node
Right *Node
}
// inorder: left, node, right
func inorder(n *Node, visit func(int)) {
if n == nil {
return
}
inorder(n.Left, visit)
visit(n.Val)
inorder(n.Right, visit)
}
// preorder: node, left, right
func preorder(n *Node, visit func(int)) {
if n == nil {
return
}
visit(n.Val)
preorder(n.Left, visit)
preorder(n.Right, visit)
}
// postorder: left, right, node
func postorder(n *Node, visit func(int)) {
if n == nil {
return
}
postorder(n.Left, visit)
postorder(n.Right, visit)
visit(n.Val)
}
func collect(walk func(*Node, func(int)), root *Node) []int {
var out []int
walk(root, func(v int) { out = append(out, v) })
return out
}
func main() {
// 1
// / \\
// 2 3
// / \\ \\
// 4 5 6
root := &Node{Val: 1,
Left: &Node{Val: 2, Left: &Node{Val: 4}, Right: &Node{Val: 5}},
Right: &Node{Val: 3, Right: &Node{Val: 6}},
}
fmt.Println("inorder: ", collect(inorder, root))
fmt.Println("preorder: ", collect(preorder, root))
fmt.Println("postorder:", collect(postorder, root))
}
Level-order traversal (BFS)
Breadth-first traversal sweeps the tree level by level, top to bottom. Instead of recursion it uses a queue: dequeue a node, visit it, then enqueue its non-nil children so the next level is processed in order.
graph LR Q["queue (FIFO)"] --> S1["dequeue node<br/>visit value"] S1 --> S2["enqueue Left,<br/>then Right"] S2 --> Q
package main
import "fmt"
type Node struct {
Val int
Left *Node
Right *Node
}
// levelOrder returns values grouped by depth, using a queue.
func levelOrder(root *Node) [][]int {
var levels [][]int
if root == nil {
return levels
}
queue := []*Node{root} // a slice used as a FIFO queue
for len(queue) > 0 {
n := len(queue) // nodes on the current level
row := make([]int, 0, n)
for i := 0; i < n; i++ {
node := queue[0] // peek front
queue = queue[1:] // dequeue
row = append(row, node.Val)
if node.Left != nil {
queue = append(queue, node.Left) // enqueue
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
levels = append(levels, row)
}
return levels
}
func main() {
root := &Node{Val: 1,
Left: &Node{Val: 2, Left: &Node{Val: 4}, Right: &Node{Val: 5}},
Right: &Node{Val: 3, Right: &Node{Val: 6}},
}
for depth, row := range levelOrder(root) {
fmt.Printf("level %d: %v\n", depth, row)
}
}
💡 Pick the traversal to fit the job
The order is not arbitrary — each one is the right tool for a task. Postorder visits children before the node, so it is how you free, delete, or compute a size/height bottom-up. Preorder is how you serialize or clone a tree top-down. Inorder has no special meaning for a plain binary tree — but on a binary search tree it emits values in sorted order, which is the whole next page.
See also
- binary search trees — add an ordering rule and the tree becomes searchable.
- heaps — a different invariant (parent ≤ children) for fast min/max.
- graphs — trees are a special case; BFS/DFS generalize there.
- stacks & queues — the queue behind level-order, the stack behind DFS.
Next: add an ordering rule and the tree becomes searchable — binary search trees.
Related topics
The BST ordering invariant (left < node < right) gives O(h) search and insert, an inorder walk yields sorted order, and balance decides log n vs n.
trees-graphsHeaps & Priority QueuesA binary heap packed in a slice — parent/child by index arithmetic, sift-up and sift-down in O(log n), and Go's container/heap to build a priority queue.
complexityBig-O & ComplexityMeasure cost before you optimize — Big-O for time and space, the common growth classes, and how to read the complexity of real Go code.
Check your understanding
Score: 0 / 51. How many children can a node in a binary tree have?
The word binary means each node has up to two children, conventionally Left and Right. Either or both can be nil, so a node may have zero, one, or two children.
2. Which depth-first traversal visits the root before either subtree?
Preorder processes the node first (pre = before its children). Inorder visits the root in the middle; postorder visits it last, which is why postorder is the natural order for freeing or deleting a tree bottom-up.
3. What data structure does level-order (breadth-first) traversal rely on?
BFS uses a FIFO queue so that nodes are processed in the order they were discovered, which sweeps the tree one level at a time. A stack (LIFO) would instead give you a depth-first walk.
4. A balanced binary tree of n nodes has height about…?
Each level of a balanced tree roughly doubles the node count, so n nodes fit in ~log₂ n levels — which is why balanced-tree operations are O(log n). If inserts make the tree chain to one side, height grows to n − 1 and it degrades to linear.
5. Which traversal is the natural order to free or delete a whole tree?
Postorder (left, right, node) guarantees children are processed before their parent — exactly what you want when destroying a tree or computing a bottom-up aggregate like height or subtree size. Preorder (node first) suits copying/serializing top-down.
Comments
Sign in with GitHub to join the discussion.