Solve vertical order & diameter variants
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
LeetCode 314. Binary Tree Vertical Order Traversal
LeetCode 543. Diameter of Binary Tree – modified to return the number of nodes (edges +
1)
https://leetcode.com/problems/binary-tree-vertical-order-traversal/description/ https://leetcode.com/problems/diameter-of-binary-tree/description/
Quick Answer: This question evaluates understanding of binary tree data structures, including traversal strategies, mapping nodes to vertical columns, and computation of tree metrics such as diameter (measured in nodes), demonstrating competency in tree algorithms and positional indexing.
Given a binary tree in level-order array form using None for missing children, return both its vertical order traversal and its diameter measured in number of nodes. Vertical order groups nodes by their column index from leftmost to rightmost; within a column, nodes are listed from top to bottom, and when multiple nodes share the same row and column, they appear in left-to-right order. If the tree is empty, return an empty vertical list and diameter 0.
Constraints
- 0 <= len(level) <= 10000
- Values are integers in the range [-1e9, 1e9]
- level[0] is not None unless the list is empty
- Level-order uses None to indicate missing children; children of None are ignored
- Output must be a dict: {"vertical": List[List[int]], "diameter": int}
- Diameter is the number of nodes on the longest path; an empty tree has diameter 0
Solution
from collections import deque, defaultdict
from typing import List, Optional, Dict, Any
class TreeNode:
__slots__ = ("val", "left", "right")
def __init__(self, val: int):
self.val = val
self.left: Optional['TreeNode'] = None
self.right: Optional['TreeNode'] = None
def _build_tree(level: List[Optional[int]]) -> Optional[TreeNode]:
if not level or level[0] is None:
return None
root = TreeNode(level[0])
q = deque([root])
i = 1
n = len(level)
while q and i < n:
node = q.popleft()
if i < n:
lv = level[i]; i += 1
if lv is not None:
node.left = TreeNode(lv)
q.append(node.left)
if i < n:
rv = level[i]; i += 1
if rv is not None:
node.right = TreeNode(rv)
q.append(node.right)
return root
def vertical_order_and_diameter(level: List[Optional[int]]) -> Dict[str, Any]:
root = _build_tree(level)
if root is None:
return {"vertical": [], "diameter": 0}
# Vertical order via BFS with column tracking
col_map = defaultdict(list)
q = deque([(root, 0)])
min_col = 0
max_col = 0
while q:
node, col = q.popleft()
col_map[col].append(node.val)
if node.left is not None:
q.append((node.left, col - 1))
if node.right is not None:
q.append((node.right, col + 1))
if col < min_col:
min_col = col
if col > max_col:
max_col = col
vertical = [col_map[c] for c in range(min_col, max_col + 1)]
# Diameter in nodes via iterative postorder computing heights
best = 0
stack = [(root, False)]
heights: Dict[TreeNode, int] = {}
while stack:
node, visited = stack.pop()
if node is None:
continue
if not visited:
stack.append((node, True))
stack.append((node.right, False))
stack.append((node.left, False))
else:
lh = heights.get(node.left, 0)
rh = heights.get(node.right, 0)
h = (lh if lh > rh else rh) + 1
heights[node] = h
total_nodes = lh + rh + 1
if total_nodes > best:
best = total_nodes
return {"vertical": vertical, "diameter": best}
Explanation
Build the tree from the level-order list using a queue, skipping children for None entries. For vertical order, run a BFS that tracks each node's column index (root at 0, left at col-1, right at col+1). Append values to a map from column to list in BFS order to ensure top-down and left-to-right ordering within a column. For the diameter in nodes, perform an iterative postorder traversal to compute each node's subtree height. At each node, the longest path going through it uses left_height + right_height + 1 nodes. Track the maximum over all nodes. The final answer combines the vertical list and the maximum path length in nodes.
Time complexity: O(n). Space complexity: O(n).
Hints
- Build the binary tree from the level-order list using a queue; ignore children of None entries.
- For vertical order, perform BFS while tracking each node's column index; append left child with col-1 and right child with col+1.
- For diameter in nodes, do a postorder traversal computing subtree heights and track max(left_height + right_height + 1).