Trees & Graphs

Trees: nodes with children

A tree is a node with a value and pointers to child nodes. A binary tree gives each node at most two children, Left and Right: type TreeNode struct { Val int; Left, Right TreeNode }. The top node is the root; nodes with no children are leaves*.

Trees are everywhere in backend work: a comment thread (replies under replies), a category hierarchy, a filesystem, a parsed JSON document. And like a linked list, a tree is self-similar — each child is the root of a smaller tree — so most tree code is recursive with a nil base case.