Views, Ancestors and Distances

// Every node's (column, row, value), sorted: columns left to right, then rows top down, then values.
void collect(TreeNode* node, int col, int row, vector<tuple<int, int, int>>& cells) {
    if (node == nullptr) return;
    cells.push_back({col, row, node->val});
    collect(node->left, col - 1, row + 1, cells);      // a left child is one column left
    collect(node->right, col + 1, row + 1, cells);     // a right child one column right
}

vector<vector<int>> verticalTraversal(TreeNode* root) {
    vector<tuple<int, int, int>> cells;
    collect(root, 0, 0, cells);
    sort(cells.begin(), cells.end());
    vector<vector<int>> columns;
    int last = INT_MIN;
    for (auto [col, row, val] : cells) {
        if (col != last) {
            columns.push_back({});
            last = col;
        }
        columns.back().push_back(val);
    }
    return columns;
}

def vertical_traversal(root):
    """Every node's (column, row, value), sorted: columns left to right, then rows top down, then values."""
    cells = []

    def collect(node, col, row):
        if node is None:
            return
        cells.append((col, row, node.val))
        collect(node.left, col - 1, row + 1)          # a left child is one column left
        collect(node.right, col + 1, row + 1)         # a right child one column right

    collect(root, 0, 0)
    cells.sort()
    columns = []
    for col, row, val in cells:
        if not columns or col != last:
            columns.append([])
            last = col
        columns[-1].append(val)
    return columns

// Every node's (column, row, value), sorted: columns left to right, then rows top down, then values.
static void collect(TreeNode node, int col, int row, List<int[]> cells) {
    if (node == null) return;
    cells.add(new int[]{col, row, node.val});
    collect(node.left, col - 1, row + 1, cells);       // a left child is one column left
    collect(node.right, col + 1, row + 1, cells);      // a right child one column right
}

static List<List<Integer>> verticalTraversal(TreeNode root) {
    List<int[]> cells = new ArrayList<>();
    collect(root, 0, 0, cells);
    cells.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] != b[1] ? a[1] - b[1] : a[2] - b[2]);
    List<List<Integer>> columns = new ArrayList<>();
    int last = Integer.MIN_VALUE;
    for (int[] c : cells) {
        if (columns.isEmpty() || c[0] != last) {
            columns.add(new ArrayList<>());
            last = c[0];
        }
        columns.get(columns.size() - 1).add(c[2]);
    }
    return columns;
}

// Every node's [column, row, value], sorted: columns left to right, then rows top down, then values.
function verticalTraversal(root) {
    const cells = [];
    function collect(node, col, row) {
        if (node === null) return;
        cells.push([col, row, node.val]);
        collect(node.left, col - 1, row + 1);          // a left child is one column left
        collect(node.right, col + 1, row + 1);         // a right child one column right
    }
    collect(root, 0, 0);
    cells.sort((a, b) => a[0] - b[0] || a[1] - b[1] || a[2] - b[2]);
    const columns = [];
    let last = null;
    for (const [col, , val] of cells) {
        if (col !== last) {
            columns.push([]);
            last = col;
        }
        columns[columns.length - 1].push(val);
    }
    return columns;
}

from collections import deque


def views(root):
    """The top and bottom views: the first and the last node in each column, in level order."""
    top, bottom, queue = {}, {}, deque([(root, 0)])
    while queue:
        node, col = queue.popleft()
        top.setdefault(col, node.val)          # the first node to reach this column, highest up
        bottom[col] = node.val                 # the latest one, lowest down
        if node.left:
            queue.append((node.left, col - 1))
        if node.right:
            queue.append((node.right, col + 1))
    columns = sorted(top)
    return [top[c] for c in columns], [bottom[c] for c in columns]

def boundary(root):
    """The root, the left edge down, the leaves left to right, the right edge back up; no node twice."""
    def is_leaf(node):
        return node.left is None and node.right is None

    out = [root.val]
    if is_leaf(root):
        return out
    node = root.left                           # the left edge, stopping before its leaf
    while node and not is_leaf(node):
        out.append(node.val)
        node = node.left if node.left else node.right

    def leaves(node):
        if node is None:
            return
        if is_leaf(node):
            out.append(node.val)
        leaves(node.left)
        leaves(node.right)

    leaves(root)
    right, node = [], root.right               # the right edge, stopping before its leaf, then reversed
    while node and not is_leaf(node):
        right.append(node.val)
        node = node.right if node.right else node.left
    return out + right[::-1]

// The deepest node with p and q both below it (a node counts as below itself).
TreeNode* lowestCommonAncestor(TreeNode* node, TreeNode* p, TreeNode* q) {
    if (node == nullptr || node == p || node == q) return node;   // nothing here, or one of the two
    TreeNode* left = lowestCommonAncestor(node->left, p, q);
    TreeNode* right = lowestCommonAncestor(node->right, p, q);
    if (left && right) return node;            // one on each side: this is where they meet
    return left ? left : right;                // pass up whatever was found
}

def lowest_common_ancestor(node, p, q):
    """The deepest node with p and q both below it (a node counts as below itself)."""
    if node is None or node is p or node is q:
        return node                            # nothing here, or one of the two
    left = lowest_common_ancestor(node.left, p, q)
    right = lowest_common_ancestor(node.right, p, q)
    if left and right:                         # one on each side: this is where they meet
        return node
    return left or right                       # pass up whatever was found

// The deepest node with p and q both below it (a node counts as below itself).
static TreeNode lowestCommonAncestor(TreeNode node, TreeNode p, TreeNode q) {
    if (node == null || node == p || node == q) return node;      // nothing here, or one of the two
    TreeNode left = lowestCommonAncestor(node.left, p, q);
    TreeNode right = lowestCommonAncestor(node.right, p, q);
    if (left != null && right != null) return node;   // one on each side: this is where they meet
    return left != null ? left : right;        // pass up whatever was found
}

// The deepest node with p and q both below it (a node counts as below itself).
function lowestCommonAncestor(node, p, q) {
    if (node === null || node === p || node === q) return node;   // nothing here, or one of the two
    const left = lowestCommonAncestor(node.left, p, q);
    const right = lowestCommonAncestor(node.right, p, q);
    if (left && right) return node;            // one on each side: this is where they meet
    return left || right;                      // pass up whatever was found
}

The lowest common ancestor of 6 and 4 — Amber marks the two nodes to find, indigo the call working, violet the calls finished, with what each handed up on its badge.

// Every node exactly k edges from target, moving up through parents as well as down.
vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
    unordered_map<TreeNode*, TreeNode*> parent{{root, nullptr}};
    vector<TreeNode*> stack{root};
    while (!stack.empty()) {                   // one walk to record every node's parent
        TreeNode* node = stack.back();
        stack.pop_back();
        for (TreeNode* child : {node->left, node->right})
            if (child) {
                parent[child] = node;
                stack.push_back(child);
            }
    }
    unordered_set<TreeNode*> seen{target};
    vector<TreeNode*> ring{target};
    for (int step = 0; step < k; step++) {     // k rings out from the target
        vector<TreeNode*> next;
        for (TreeNode* node : ring)
            for (TreeNode* near : {node->left, node->right, parent[node]})
                if (near && seen.insert(near).second) next.push_back(near);
        ring = next;
    }
    vector<int> out;
    for (TreeNode* node : ring) out.push_back(node->val);
    return out;
}

def distance_k(root, target, k):
    """Every node exactly k edges from target, moving up through parents as well as down."""
    parent, stack = {root: None}, [root]
    while stack:                               # one walk to record every node's parent
        node = stack.pop()
        for child in (node.left, node.right):
            if child:
                parent[child] = node
                stack.append(child)
    seen, ring = {target}, [target]
    for _ in range(k):                         # k rings out from the target
        nxt = []
        for node in ring:
            for near in (node.left, node.right, parent[node]):
                if near and near not in seen:
                    seen.add(near)
                    nxt.append(near)
        ring = nxt
    return [node.val for node in ring]

// Every node exactly k edges from target, moving up through parents as well as down.
static List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
    Map<TreeNode, TreeNode> parent = new HashMap<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    parent.put(root, null);
    stack.push(root);
    while (!stack.isEmpty()) {                 // one walk to record every node's parent
        TreeNode node = stack.pop();
        for (TreeNode child : new TreeNode[]{node.left, node.right})
            if (child != null) {
                parent.put(child, node);
                stack.push(child);
            }
    }
    Set<TreeNode> seen = new HashSet<>(List.of(target));
    List<TreeNode> ring = new ArrayList<>(List.of(target));
    for (int step = 0; step < k; step++) {     // k rings out from the target
        List<TreeNode> next = new ArrayList<>();
        for (TreeNode node : ring)
            for (TreeNode near : new TreeNode[]{node.left, node.right, parent.get(node)})
                if (near != null && seen.add(near)) next.add(near);
        ring = next;
    }
    List<Integer> out = new ArrayList<>();
    for (TreeNode node : ring) out.add(node.val);
    return out;
}

// Every node exactly k edges from target, moving up through parents as well as down.
function distanceK(root, target, k) {
    const parent = new Map([[root, null]]);
    const stack = [root];
    while (stack.length) {                     // one walk to record every node's parent
        const node = stack.pop();
        for (const child of [node.left, node.right])
            if (child) {
                parent.set(child, node);
                stack.push(child);
            }
    }
    const seen = new Set([target]);
    let ring = [target];
    for (let step = 0; step < k; step++) {     // k rings out from the target
        const next = [];
        for (const node of ring)
            for (const near of [node.left, node.right, parent.get(node)])
                if (near && !seen.has(near)) {
                    seen.add(near);
                    next.push(near);
                }
        ring = next;
    }
    return ring.map((node) => node.val);
}

Rings out from 5 — Indigo is the target; green the ring just reached; violet the rings before it. The badge is each node's distance from 5.

def time_to_burn(root, start):
    """Minutes for a fire lit at `start` to reach every node, one edge a minute in every direction."""
    parent, stack, origin = {root: None}, [root], None
    while stack:
        node = stack.pop()
        if node.val == start:
            origin = node
        for child in (node.left, node.right):
            if child:
                parent[child] = node
                stack.append(child)
    seen, ring, minutes = {origin}, [origin], 0
    while True:
        nxt = []
        for node in ring:
            for near in (node.left, node.right, parent[node]):
                if near and near not in seen:
                    seen.add(near)
                    nxt.append(near)
        if not nxt:
            return minutes
        ring, minutes = nxt, minutes + 1

def top_view(root):
    top = {}

    def walk(node, col):
        if node is None:
            return
        top.setdefault(col, node.val)          # wrong: the first visit isn't the highest node
        walk(node.left, col - 1)
        walk(node.right, col + 1)

    walk(root, 0)
    return [top[c] for c in sorted(top)]

def vertical_traversal(root):
    """Every node's (column, row, value), sorted: columns left to right, then rows top down, then values."""
    cells = []

    def collect(node, col, row):
        if node is None:
            return
        cells.append((col, row, node.val))
        collect(node.left, col - 1, row + 1)          # a left child is one column left
        collect(node.right, col + 1, row + 1)         # a right child one column right

    collect(root, 0, 0)
    cells.sort(key=lambda c: (c[0], c[1]))     # wrong: two nodes sharing a row stay in visit order
    columns = []
    for col, row, val in cells:
        if not columns or col != last:
            columns.append([])
            last = col
        columns[-1].append(val)
    return columns

def lowest_common_ancestor(node, p, q):
    if p.val < node.val and q.val < node.val:  # wrong: the BST rule, on a tree with no order
        return lowest_common_ancestor(node.left, p, q)
    if p.val > node.val and q.val > node.val:
        return lowest_common_ancestor(node.right, p, q)
    return node

def distance_k(root, target, k):
    """Every node exactly k edges from target, moving up through parents as well as down."""
    parent, stack = {root: None}, [root]
    while stack:                               # one walk to record every node's parent
        node = stack.pop()
        for child in (node.left, node.right):
            if child:
                parent[child] = node
                stack.append(child)
    seen, ring = {target}, [target]
    for _ in range(k):                         # k rings out from the target
        nxt = []
        for node in ring:
            for near in (node.left, node.right, parent[node]):
                if near:                       # wrong: nothing stops the walk turning back
                    nxt.append(near)
        ring = nxt
    return [node.val for node in ring]

def boundary(root):
    """The root, the left edge down, the leaves left to right, the right edge back up; no node twice."""
    def is_leaf(node):
        return node.left is None and node.right is None

    out = [root.val]
    if is_leaf(root):
        return out
    node = root.left                           # the left edge, stopping before its leaf
    while node:                                # wrong: walks on into the leaf
        out.append(node.val)
        node = node.left if node.left else node.right

    def leaves(node):
        if node is None:
            return
        if is_leaf(node):
            out.append(node.val)
        leaves(node.left)
        leaves(node.right)

    leaves(root)
    right, node = [], root.right               # the right edge, stopping before its leaf, then reversed
    while node and not is_leaf(node):
        right.append(node.val)
        node = node.right if node.right else node.left
    return out + right[::-1]