CodeGround
DashboardProblemsInterviewsAssessmentsCourses
CodeGround
DashboardProblemsInterviewsAssessmentsCourses
The Technical Interview Course

0 of 170 lessons complete

  • Recursion, properly
  • The tree recursion template
  • Combining what the children return
  • A recursion that calls another recursion
  • Computing once instead of at every node
  • Return one thing, update another
  • Going across instead of down
  • Carrying information down the tree
  • Search trees and the ordering you can exploit
  • Rebuilding a tree from its traversals
  • The two-quantity pattern at full strength
  • Writing a tree down and reading it back
  • Retrieval: which traversal, which direction?

Recursion and Trees

80 / 170

Recursion and Trees/Lesson 13 of 13·About 50 min

Retrieval: which traversal, which direction?

Two problems rebuilt cold, plus the three questions that decide the shape of any tree solution.

Key idea

Ask these before writing anything

Does the question care about levels? If yes, use a queue and snapshot its length. If no, recursion is almost always shorter.

Does a node need something from above, something from below, or both? From above is a parameter, from below is a return value, and both is both. Naming them turns the function signature into a decision rather than a guess.

Is the answer necessarily rooted at the node it passes through? If not, you need the two-quantity split: return one thing, update another.

Tip

And one more for search trees

If the tree is a search tree and your solution visits every node, look again. The ordering usually lets you descend one path instead, and in-order traversal usually turns the question into one about a sorted sequence.

Quick check· 5 min

What shape does this need?

Find the largest sum of any root-to-leaf path in a binary tree whose values may be negative. What shape does the solution take?

Problem· 15 min

Diameter of Binary Tree, from scratch

You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.

Problem· 25 min

LRU Cache, from scratch

You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.

PreviousWriting a tree down and reading it back
NextThe smallest thing, cheaply

0 of 4 parts complete