Day 23: Maximum Depth of Binary Tree

Day 23 — Maximum Depth of Binary Tree

Coding problem

Solution outline (coding)

• DFS: depth = 1 + max(left_depth, right_depth).
• BFS: level-order with a queue; increment depth each level.
• Handle empty tree → 0.

Time complexity: O(n) — visit all nodes.

Space complexity: O(h) DFS stack or O(w) BFS queue width.

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 maxDepth(self, root: Optional[TreeNode]) -> int:
    if not root:
      return 0
    return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))


# Input:  tree [3,9,20,null,null,15,7]
# Output: 3

SQL interview practice

1. Interview question

Companies / track: Google

Google: SQL screens usually assume BigQuery, Ads / Search / YouTube-style fact tables, and talking through bytes processed and partition pruning.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Google**-scale surfaces (ads, product, or engagement — as the tables suggest).
hierarchy(employee_id, manager_id). BigQuery: using recursive CTE, compute depth per employee (distance from root) and max depth per org.

Tables implied by the prompt:

• hierarchy(employee_id, manager_id)
• employee(distance from root)

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 / BFS 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 reach AS (
  SELECT employee_id, manager_id, 0 AS depth
  FROM hierarchy
  WHERE manager_id IS NULL
  UNION ALL
  SELECT h.employee_id, h.manager_id, r.depth + 1
  FROM hierarchy AS h
  JOIN reach AS r ON h.manager_id = r.employee_id
)
SELECT employee_id, MAX(depth) AS depth_from_root
FROM reach
GROUP BY employee_id;