Trees & recursive DFS

Trees: DFS & BFS, lesson 1 of 3

Trees & recursive DFS

Read tree notation, build trees, and solve problems by asking what each call returns.

13 min, 0 of 4 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

A binary tree is a set of nodes where each node holds a value and points to at most two children, left and right. The top node is the root; a node with no children is a leaf.

        3          <- root (depth 1)
       / \
      9   20
         /  \
        15   7     <- leaves

In Python (and on LeetCode) a node is a tiny class:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

An empty tree is just None. That fact powers every recursive tree function you'll write.

Level-order notation. Problems describe trees as a list read row by row, left to right, with None for a missing child. The tree above is:

[3, 9, 20, None, None, 15, 7]

Row 1 is 3. Row 2 is 9, 20. Row 3 lists the children of 9 (None, None) and then of 20 (15, 7). Children of a None are never listed, and trailing Nones are dropped.

Example

TreeNode and a build helper

build walks the list with a queue, handing out values to each node's left and right in turn. In the practice problems the tests build the tree for you; in lessons we bring our own helper.

Quiz

Which level-order list describes this tree?

The one question: what does each call return?

A tree is recursive: every child is the root of a smaller tree. So pick a function contract like "max_depth(node) returns the depth of the subtree rooted at node", then:

  1. Base case: node is None (empty tree). Return the answer for nothing: 0, True, []...
  2. Trust the recursion: call it on node.left and node.right and assume the answers are right.
  3. Combine: build this node's answer from the two child answers and node.val.

This is depth-first search (DFS): you go all the way down one branch before trying the next.

Example

Max depth, with a trace

Leaves return 1 (1 + max(0, 0)), 20 returns 2, and the root returns 1 + max(1, 2) = 3. Answers flow up from the leaves. Every node is visited once, so it's O(n) time and O(h) stack space, where h is the tree's height.

Pre-, in- and post-order are the same DFS; they differ only in when you handle the node relative to the two recursive calls:

  • pre-order: node, left, right (copying a tree, passing info down)
  • in-order: left, node, right (BSTs: gives the values sorted)
  • post-order: left, right, node (you need the children's answers first: height, sums)
Example

The three orders

Only the position of out.append moves. Try writing each order out by hand before running it.

Quiz

What does this print?

Quiz

You need each node's subtree size before you can process the node itself. Which order fits?

Exercise

Count the leaves

Write a recursive count_leaves(root) that returns how many leaves (nodes with no children) the tree has. An empty tree has 0 leaves.

[3, 9, 20, None, None, 15, 7] has 3 leaves: 9, 15 and 7.