Course contentsShow
← Computer Science
Lesson 948 of 2,87222. Dynamic ProgrammingFree lesson

DP on Binary Trees

Solving problems on binary trees with state defined at each node combining left and right subtree results.

DP on Binary Trees

You'll learn how to solve optimization problems on binary trees by defining dynamic programming states at each node that combine information from its left and right subtrees.

The Core Idea

In DP on binary trees, you recursively compute optimal solutions for each node by:

  1. Solving the problem for the left subtree
  2. Solving the problem for the right subtree
  3. Combining those results at the current node based on your problem's requirements

The state at each node typically tracks different scenarios (like "include this node" vs "exclude this node") and merges the best outcomes from both children.

How It Works

Think of it like calculating a company's total value. Each department (node) reports two numbers to its manager: "value if we participate in the project" and "value if we don't." The manager combines these reports from both teams below them, adds their own contribution, and passes it upward. The CEO at the root makes the final decision based on all aggregated information.

Binary tree specificity: Unlike general trees, each node has at most two children, simplifying your state transitions—you only combine left and right results.

Typical Pattern

For each node, you might track:

  • Best result including this node
  • Best result excluding this node

Then recursively:

result[node] = combine(result[left_child], result[right_child], node.value)

The base case is always the leaf nodes (or null children), where you return simple initial values.

Common Applications

  • Maximum path sum in a binary tree
  • House robber on trees (can't pick adjacent nodes)
  • Binary tree cameras placement
  • Vertex cover on binary trees

Key Takeaway: DP on binary trees leverages the natural recursive structure of trees, defining states at each node that intelligently merge left and right subtree solutions to build the global optimum.