AlgoViz
HomeBinary Trees

Introduction to Trees

Easy

A root, and up to two children each

Problem

Learn the binary tree: a root node with up to two children (left/right); nodes with no children are leaves.

In simple words

An upside-down tree: one root splits into left and right branches down to the leaves.

The idea

A binary tree is a node holding a value and references to a left and a right child, each of which roots a binary tree of its own. That self-similarity is why almost every tree algorithm is three lines: handle the empty case, recurse on both sides, combine.

The trick

  • Height is the longest root-to-leaf path; a balanced tree has height O(log n).
  • Every recursive tree function needs a null base case first.
  • Solve left, solve right, combine — the shape of nearly all of them.
123456

Step 1 of 8. Inorder = Left → Node → Right. We dive left first, emit the node, then go right.

1/8
Optimal
timeO(n)spaceO(h)

Order = when you emit the node.

1function inorder(node) {2  if (!node) return;3  inorder(node.left);4  visit(node.val);        // node between children5  inorder(node.right);6}

Input

nodes
6, 5 edges

Output

output
—
inorder
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
[1,2,3]
Output:
1 with children 2,3

Finished the walkthrough? Add it to your streak.