Compute binary tree left-side view
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Given a binary tree, return the values visible from the left side when looking from top to bottom. If multiple nodes exist at the same depth, the leftmost node is visible. Provide iterative (level-order) and recursive solutions, discuss time and space complexity, and handle skewed trees and missing children.
Quick Answer: This question evaluates understanding of binary tree traversal and level-order reasoning, including distinctions between recursive and iterative approaches and handling of edge cases such as skewed or missing children.
Given level-order tree values, return the leftmost visible value at each depth.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([1,2,3,None,5,None,4],)
Expected Output: [1, 2, 5]
Explanation: Left view through sparse tree.
Input: ([],)
Expected Output: []
Explanation: Empty tree.
Input: ([1,None,2,None,None,3],)
Expected Output: [1, 2, 3]
Explanation: Missing left child.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.