Skip to content
← All Patterns
← Longest Common SubsequenceMonotonic Stack/Queue →
Dynamic ProgrammingAdvanced

DP on Trees

Apply dynamic programming on tree structures using post-order DFS, where each node's answer depends on its children's answers.

Problem: Diameter of Binary Tree

Find the length of the longest path between any two nodes using post-order DFS with DP.

1
2
3
4
5
DefaultVisitingVisited

Visit root node 1

Start post-order DFS at root. Will compute depths of left and right subtrees.

Current Diameter (Max Path Length)
0
Step 1/8
Speed:

When to Use

  • Optimal value on tree paths
  • Tree diameter
  • Maximum path sum
  • House robber on tree

Key Indicators

  • Tree + optimization
  • Path sum in tree
  • Subtree-dependent decisions

Complexity

Time

O(n)

Space

O(n)

Common Problems

Binary Tree Maximum Path SumHouse Robber IIIDiameter of Binary TreeLongest Path With Different Adjacent Characters

Code

def dfs(node):
    if not node: return 0
    left = dfs(node.left)
    right = dfs(node.right)
    # update global answer with left + right + node.val
    return max(left, right) + node.val

Want all 29 patterns with detailed visual walkthroughs?

The complete book includes 84 practice problems, full decision tree, and illustrated step-by-step solutions.

Book Coming Soon ($4.99)