Dynamic Programming on Trees Interview Patterns

By /

Core Pattern

Tree DP follows a single structural pattern: post-order DFS. You recurse into children first, then compute the answer for the current node using the values returned from children. Each DFS call returns whatever information the parent needs to compute its own answer. The global answer is often tracked in a nonlocal variable updated at each node.

Template structure:

  • Define what each DFS call returns (depth, max gain, a tuple of states, etc.).
  • Handle the base case: None node returns a safe default (0, -inf, or a tuple of neutral values).
  • Recurse left and right to get children’s return values.
  • Combine children’s values to compute (a) the current node’s return value and (b) any update to the global answer.

Diameter of Binary Tree (LC 543)

The diameter is the longest path between any two nodes. The path may or may not pass through the root. At each node, the longest path through that node equals left_depth + right_depth. The DFS returns depth; the global answer tracks the max diameter seen.

class Solution:
    def diameterOfBinaryTree(self, root) -> int:
        self.ans = 0

        def dfs(node):
            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            # path through this node
            self.ans = max(self.ans, left + right)
            # return depth to parent
            return 1 + max(left, right)

        dfs(root)
        return self.ans

Time: O(n). Space: O(h) call stack. The trick: the return value (depth) differs from what we track globally (diameter).

Maximum Path Sum (LC 124)

The path can start and end at any node. At each node, the max gain from going into that subtree is node.val + max(0, best_from_left, best_from_right) – we only extend into a child if it adds positive value. The path through the current node (which cannot be extended further up) is node.val + max(0, left) + max(0, right).

class Solution:
    def maxPathSum(self, root) -> int:
        self.ans = float('-inf')

        def dfs(node):
            if not node:
                return 0
            # discard negative contributions from children
            left = max(0, dfs(node.left))
            right = max(0, dfs(node.right))
            # path that passes through this node (cannot extend up further)
            self.ans = max(self.ans, node.val + left + right)
            # return max gain extendable to parent (one direction only)
            return node.val + max(left, right)

        dfs(root)
        return self.ans

Key insight: when returning to the parent, you can only extend the path in one direction (left or right), not both. You pass both into the global answer update but only one back to the parent.

House Robber III (LC 337)

Cannot rob two adjacent nodes (parent-child). At each node, return a pair (rob_this, skip_this). If we rob the current node, we cannot rob its children. If we skip it, we take the best option for each child independently.

class Solution:
    def rob(self, root) -> int:

        def dfs(node):
            if not node:
                return (0, 0)  # (rob, skip)

            left_rob, left_skip = dfs(node.left)
            right_rob, right_skip = dfs(node.right)

            # rob this node: must skip both children
            rob_this = node.val + left_skip + right_skip
            # skip this node: children can be robbed or skipped, take best
            skip_this = max(left_rob, left_skip) + max(right_rob, right_skip)

            return (rob_this, skip_this)

        return max(dfs(root))

No global variable needed here – the answer is max(rob_root, skip_root). Returning a tuple of states is the hallmark of state-machine tree DP.

Binary Tree Cameras (LC 968)

Place minimum cameras such that every node is monitored. A camera at a node covers that node, its parent, and its children. Use 3-state DP at each node:

  • 0 – NOT_COVERED: Node is not covered and has no camera.
  • 1 – HAS_CAMERA: Node has a camera (covers itself, parent, and children).
  • 2 – COVERED: Node is covered but has no camera.
class Solution:
    def minCameraCover(self, root) -> int:
        self.cameras = 0
        NOT_COVERED, HAS_CAMERA, COVERED = 0, 1, 2

        def dfs(node):
            if not node:
                # null nodes are considered covered (don't need cameras)
                return COVERED

            left = dfs(node.left)
            right = dfs(node.right)

            # if any child is not covered, must place camera here
            if left == NOT_COVERED or right == NOT_COVERED:
                self.cameras += 1
                return HAS_CAMERA

            # if any child has a camera, this node is covered
            if left == HAS_CAMERA or right == HAS_CAMERA:
                return COVERED

            # both children are covered but no camera pointing at this node
            return NOT_COVERED

        # if root itself is not covered, place a camera there
        if dfs(root) == NOT_COVERED:
            self.cameras += 1

        return self.cameras

Greedy insight embedded in DP: place cameras at the lowest possible nodes (leaves’ parents) to cover as much as possible per camera.

Count Good Nodes in Binary Tree (LC 1448)

A node is “good” if no node on the path from root to that node has a greater value. This one passes state downward rather than returning it upward – pass max_so_far as a parameter.

class Solution:
    def goodNodes(self, root) -> int:
        def dfs(node, max_so_far):
            if not node:
                return 0
            good = 1 if node.val >= max_so_far else 0
            new_max = max(max_so_far, node.val)
            return good + dfs(node.left, new_max) + dfs(node.right, new_max)

        return dfs(root, float('-inf'))

Longest Univalue Path (LC 687)

Longest path where all nodes have the same value. Similar structure to diameter: DFS returns the longest chain going down, global answer tracks the longest path through the current node.

class Solution:
    def longestUnivaluePath(self, root) -> int:
        self.ans = 0

        def dfs(node):
            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            # only extend into child if value matches
            left_path = (left + 1) if node.left and node.left.val == node.val else 0
            right_path = (right + 1) if node.right and node.right.val == node.val else 0
            self.ans = max(self.ans, left_path + right_path)
            return max(left_path, right_path)

        dfs(root)
        return self.ans

General Template

Before writing any tree DP solution, answer these questions:

  • What does DFS return? A single value, a tuple of states, or nothing (side-effect only)?
  • What is the base case for None? Return 0 for counts/depths, -inf for maxima, a neutral tuple for state machines.
  • What is the global answer? Often the answer cannot be returned directly up the tree – track it in a nonlocal or self variable.
  • Is state passed down or returned up? Most tree DP returns values up (post-order). Passing state down (pre-order) is used when decisions depend on ancestors.
# Universal tree DP template
def solve(root):
    ans = [neutral_value]  # or use nonlocal

    def dfs(node):
        if not node:
            return base_case

        left_val = dfs(node.left)
        right_val = dfs(node.right)

        # Update global answer using node + children info
        ans[0] = max(ans[0], combine_for_global(node, left_val, right_val))

        # Return value for parent to use
        return combine_for_parent(node, left_val, right_val)

    dfs(root)
    return ans[0]
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the general pattern for DP on binary trees?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Tree DP uses post-order DFS: solve subproblems for left and right children first, then combine to solve for the current node. Each DFS call returns the information the parent needs. The global answer is often tracked as a nonlocal variable updated at each node. Template: def dfs(node): if not node: return BASE_CASE. left_info = dfs(node.left). right_info = dfs(node.right). Update global answer using node.val + left_info + right_info. Return the info the parent needs (often a subset of what was computed locally). The critical insight: what the parent needs and what is needed to compute the global answer at this node may differ – return what the parent needs, track the global answer separately.”}},{“@type”:”Question”,”name”:”How do you find the diameter of a binary tree?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The diameter through a node = depth of left subtree + depth of right subtree. The diameter of the tree = maximum over all nodes of this value. Post-order DFS: define dfs(node) returning the depth of the subtree rooted at node. At each node: left_depth = dfs(node.left), right_depth = dfs(node.right). Update max_diameter = max(max_diameter, left_depth + right_depth). Return 1 + max(left_depth, right_depth) to the parent. The function returns depth (what the parent needs to compute its diameter), while the global max_diameter tracks the answer. This is LC 543. The same pattern extends to LC 124 (Maximum Path Sum) by replacing depth with maximum gain.”}},{“@type”:”Question”,”name”:”How does the House Robber III solution work on a tree?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”At each node, two choices: rob this house (cannot rob direct children) or skip it (children can be either robbed or not). Return a pair (rob, skip) from each DFS call. rob = node.val + left_skip + right_skip (rob this, so children must be skipped). skip = max(left_rob, left_skip) + max(right_rob, right_skip) (skip this, so each child independently chooses the better option). Base case: return (0, 0) for None node. Final answer: max(dfs(root)). This is O(n) vs the O(n^2) naive approach of re-computing each subtree with and without each node. The pair-return pattern generalizes to any tree DP with multiple states per node.”}},{“@type”:”Question”,”name”:”How do you solve Binary Tree Cameras (LC 968)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Each node can be in one of 3 states: NOT_COVERED (no camera covers this node), COVERED_NO_CAMERA (covered by a child camera), HAS_CAMERA (this node has a camera). Post-order DFS computes the state for each subtree. Transitions: if either child is NOT_COVERED, this node must have a camera (HAS_CAMERA). If any child has a camera (HAS_CAMERA), this node is COVERED_NO_CAMERA. Otherwise (both children are COVERED_NO_CAMERA), this node is NOT_COVERED (optimistically defer the camera to the parent). After the DFS, if the root is NOT_COVERED, add one more camera. Greedy insight: place cameras at internal nodes rather than leaves to maximize coverage per camera.”}},{“@type”:”Question”,”name”:”When should you use tree DP vs a simple DFS traversal?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use tree DP when: (1) The answer at a node depends on answers from both subtrees (diameter, path sum, robber). (2) You need to make a choice at each node that affects the valid choices at ancestors or descendants (cameras, coloring). (3) The optimal structure at a node cannot be determined in a single top-down pass. Use simple DFS traversal when: (1) You only need information passed down (path from root, accumulated sum). (2) Each node's contribution is independent of subtree structure. (3) Problems like "sum of paths from root to leaves" or "count nodes at depth k." The distinguishing question: does computing the answer for a node require knowing the answers from both its children? If yes, use post-order tree DP.”}}]}

Meta coding interviews frequently test tree DP patterns. See common questions for Meta interview: tree DP and binary tree problems.

Databricks interviews include tree DP and recursive data structures. See patterns for Databricks interview: tree and recursive DP problems.

Atlassian coding rounds include tree DP patterns. See common questions for Atlassian interview: tree traversal and DP problems.

Scroll to Top