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/
Overview: 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
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).