Trees: Practice

Trees

A tree branches from a single root into parent and child nodes, so data naturally nests instead of sitting in a flat line.

12453

Loading visual…

Definition

A tree is made of nodes connected by edges, starting from a single root node at the top. Every node except the root has exactly one parent, and a node can have any number of children (in a binary tree, at most two, usually called left and right). A node with no children is a leaf. The depth of a node is how many edges separate it from the root, and the height of the tree is the depth of its deepest leaf, so a tree with just a root has height 0 and a tree branching three levels deep has height 2. Because each child is itself the root of its own smaller tree, trees are naturally processed with recursion: a function that handles one node and then calls itself on that node's children walks the whole structure without any special-casing for how deep it goes. Visiting every node in a tree is called a traversal, and there are two families of traversal. Depth-first traversals (pre-order, in-order, post-order) follow one branch all the way down before backtracking, usually implemented with recursion or an explicit stack. Breadth-first traversal (level-order) visits every node at the current depth before moving to the next depth, which needs a queue instead of a stack. The traversal you pick changes the order values come out in, even though every traversal visits the same set of nodes exactly once.

Examples

function treeSum(node) {
  if (!node) return 0;
  return node.value + treeSum(node.left) + treeSum(node.right);
}
const tree = { value: 1, left: { value: 2, left: null, right: null }, right: { value: 3, left: null, right: null } };
treeSum(tree); // 6

Each call handles one node's own value and then recurses on its left and right children, so the whole tree is summed without tracking depth explicitly.

function preOrder(node, out = []) {
  if (!node) return out;
  out.push(node.value);
  preOrder(node.left, out);
  preOrder(node.right, out);
  return out;
}
preOrder(tree); // [1, 2, 3] for the tree above

The node's own value is recorded before either child is visited, which is what makes this a pre-order (root, then left, then right) traversal.

function levelOrder(root) {
  const queue = [root];
  const order = [];
  while (queue.length) {
    const node = queue.shift();
    if (!node) continue;
    order.push(node.value);
    queue.push(node.left, node.right);
  }
  return order;
}

A queue instead of recursion makes the traversal breadth-first: every node at the current depth is dequeued and its children enqueued before any node at the next depth is visited.

Common mistakes

Forgetting the base case (a null child) in a recursive traversal, causing infinite recursion or a crash.
Assuming every traversal returns values in the same order; pre-order, in-order, post-order, and level-order all produce different sequences from the same tree.
Mixing up depth (distance from the root) and height (distance to the deepest leaf); they are measured from opposite ends.

Key takeaways

A tree branches from one root into parent and child nodes, with leaves as the nodes that have no children.
Depth-first traversals use recursion or a stack; breadth-first traversal uses a queue and visits level by level.
Because every subtree is itself a tree, recursive functions are the natural way to process one.

Check your understanding

A binary tree's traversal visits the root, then its left subtree, then its right subtree. What is that traversal called?

Where you see this

The DOM is a tree of nested HTML elements, and rendering walks it from the root down.
File systems nest folders inside folders, each folder a node with files and subfolders as children.
JSON and other nested data, and the abstract syntax trees parsers build from source code.
Org charts and category hierarchies, where each item has exactly one parent above it.

Practice this

Max Depth (easy)Sum of Nodes (easy)Count Nodes (easy)Maximum Value (medium)