DSA Factory
All free lessons
Level 3 · Structures

Free Trees lessons

12 lessons, about 121 minutes in all. Each teaches one idea with a visual, then gives you one problem built for it. Read the lessons here, then create a free account to solve the problems and keep your progress.

Start free with lesson 1See the full Trees path

Stage 0Nodes and depth

  1. Count the nodesAnswer 0 for an empty tree, and 1 plus left and right counts for every node.8 min
  2. Maximum depthThe depth of a tree is 1 plus the maximum depth of its two subtrees.8 min
  3. Search a binary treeCheck the root value, and if it doesn't match, check either the left or right subtree.8 min
  4. Same treeWalk two trees simultaneously, checking structure and values at every node.9 min

Stage 1Traversals

  1. Preorder traversalVisit the root first, then everything in the left subtree, then everything in the right subtree.8 min
  2. Inorder traversalVisit the left subtree, then the root, then the right subtree — the order that sorts a BST for free.8 min
  3. Postorder traversalVisit both children before the root — the order to use whenever a node's answer needs its children's answers first.8 min
  4. Iterative inorder traversalDo the same left-root-right walk with your own stack instead of the recursive call stack.12 min

Stage 2Level order

  1. Read the tree row by rowList the nodes of a binary tree one level at a time, using a queue and counting how many nodes are in the current row.14 min
  2. Zigzag through the rowsRead the rows of a tree left to right, then right to left, alternating, by flipping every second row after the level order walk.12 min
  3. The biggest value in each rowFind the largest value on every level of a tree by keeping a running maximum for the row while the queue is processed.12 min
  4. Is the tree filled without gapsCheck whether a binary tree is complete - every level full except possibly the last, which fills from the left - using a row-by-row walk that notices the first gap.14 min

There’s more after this

These are the opening stages of Trees. The full path climbs on to harder problems and a mastery test. Create a free account and we’ll keep your place.

Start the full path free