Day 51: Binary Tree Max Path Sum

Day 51 — Binary Tree Max Path Sum

Coding problem

Solution outline (coding)

• Post-order DFS: for each node, compute max single-path gain through one child.
• Global max = max of left_gain + right_gain + node.val at each node (clamped negatives to 0).
• Return max path sum seen.

Time complexity: O(n) — one DFS.

Space complexity: O(h) — stack.

from typing import Optional


class TreeNode:
  def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right


class Solution:
  def maxPathSum(self, root: Optional[TreeNode]) -> int:
    self.best = float('-inf')

    def dfs(n: Optional[TreeNode]) -> int:
      if not n:
        return 0
      left = max(0, dfs(n.left))
      right = max(0, dfs(n.right))
      self.best = max(self.best, n.val + left + right)
      return n.val + max(left, right)

    dfs(root)
    return self.best


# Input:  tree [-10,9,20,null,null,15,7]
# Output: 42

SQL interview practice

1. Interview question

Companies / track: Meta, Google

Meta and Google both lean on ads and product surfaces: event streams, CTR-style rates, windowed metrics, and careful handling of identity joins.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Meta, Google**-scale surfaces (ads, product, or engagement — as the tables suggest).
tree_paths(tree_id, node_id, value, parent_id). BigQuery: compute maximum path sum from any node to any node per tree.

Tables implied by the prompt:

• tree_paths(tree_id, node_id, value, parent_id)

Engine: BigQuery — use its date, array, and approximate functions as documented.

2. Solution outline

• Clarify out loud: result grain (one row per what?), join keys, time zone, and any ORDER BY / LIMIT / tie-breakers.
• Map DFS to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

WITH RECURSIVE walk AS (
  SELECT tree_id, node_id, parent_id, value, value AS path_sum, 1 AS depth
  FROM tree_paths WHERE parent_id IS NULL
  UNION ALL
  SELECT t.tree_id, t.node_id, t.parent_id, t.value, w.path_sum + t.value, w.depth + 1
  FROM tree_paths AS t
  JOIN walk AS w ON t.parent_id = w.node_id AND t.tree_id = w.tree_id
)
SELECT tree_id, MAX(path_sum) AS max_downward_path FROM walk GROUP BY tree_id;