Day 22: Invert Binary Tree

Day 22 — Invert Binary Tree

Coding problem

Solution outline (coding)

• DFS or BFS: at each node, swap left and right children.
• Recurse on subtrees (or use a queue for level order).
• Base case: None returns None.

Time complexity: O(n) — every node visited once.

Space complexity: O(h) recursion stack; h = height (worst O(n) skewed tree).

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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root:
      return None
    root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
    return root


# Input:  tree [4,2,7,1,3,6,9]
# Output: inverted tree [4,7,2,9,6,3,1]

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).
tree_nodes(tree_id, node_id, parent_id, left_right_flag). BigQuery: produce a view that shows swapped left/right children for each tree (logical inversion) and validate structure invariants.

Tables implied by the prompt:

• tree_nodes(tree_id, node_id, parent_id, left_right_flag)
• tree(logical inversion)

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).
• Windows: align PARTITION BY / ORDER BY with the business rule; use QUALIFY in BigQuery when you need top-N per group.
• Arrays / UDFs: UNNEST and offsets for index; say when logic belongs in SQL vs a UDF.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

WITH edges AS (
  SELECT tree_id, node_id, parent_id, left_right_flag
  FROM tree_nodes
),
swapped AS (
  SELECT tree_id, node_id, parent_id,
    CASE WHEN left_right_flag = 'L' THEN 'R' WHEN left_right_flag = 'R' THEN 'L' ELSE left_right_flag END AS inv_flag
  FROM edges
)
SELECT * FROM swapped;