TRT
Sign in

Core · Module 10 · Lesson 4 of 5

Tree recursion patterns

Most tree problems are solved by one of three recursive shapes: combine the children's answers on the way up, pass information down from the root, or return one value while updating a global best.

Pro — members onlyAbout 14 minutes

By the end you can

  • Solve problems bottom-up by combining the answers of the two subtrees
  • Solve problems top-down by passing information from the root toward the leaves
  • Return one value while tracking another, as in the diameter and maximum path sum

Builds on Insert and delete.

01 · A question first

The diameter of a tree is the longest path between any two of its nodes, and it doesn't have to pass through the root. A function that only computes the height of each subtree can still find it in a single pass. How?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • One function, one subtree
  • Shape 1: bottom-up
  • Shape 2: top-down
  • Shape 3: return one thing, record another
  • Returning a node: the lowest common ancestor
  • Working with two trees at once
  • Choosing the shape
  • Pseudocode & Multi-Language Implementations (C++, Java, Python)
See plansAlready a member? Sign in

03 · Practice

Practice · easy · LeetCodeSame treeDecide whether two binary trees have the same shape and the same values, by recursing on both at once.Practice · easy · LeetCodeSubtree of another treeDecide whether one tree appears as a subtree of another, by running a same-tree check from every node.Practice · easy · LeetCodeBalanced binary treeDecide whether every node's subtrees differ in height by at most one, in a single O(n) pass.Practice · easy · LeetCodeDiameter of binary treeFind the longest path between any two nodes by returning heights and recording the best path through each node.Practice · medium · LeetCodeCount good nodes in binary treeCount nodes that are at least as large as every node on the path from the root, passing the running maximum down.Practice · hard · LeetCodeBinary tree maximum path sumFind the path with the largest sum of values anywhere in the tree, returning the best downward branch and recording the best turning path.

Asked in interviews

Something wrong with this lesson? Report a problem