Implement tree left/right views via BFS and DFS
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a binary tree, output the left view and right view: for each depth, the first node visible from the left and the first node visible from the right. Implement two solutions:
(a) a BFS level-order traversal; and
(b) a DFS with depth tracking. Provide time and space complexity for both approaches. Dry-run your logic on edge cases including an empty tree, a single-node tree, skewed (left/right) trees, and balanced trees to verify ordering of nodes per level.
Quick Answer: This question evaluates understanding of binary tree traversal techniques and algorithmic reasoning for producing per-depth left and right views, assessing competencies in data structures, traversal ordering, and correctness across edge cases.
Given a binary tree (provided as a level-order array using `null`/`None` markers for missing children, LeetCode-style), return its **left view** and **right view**.
- The **left view** is the list of the first node seen at each depth when looking at the tree from the left (the leftmost node of every level), ordered from the root's level downward.
- The **right view** is the list of the first node seen at each depth from the right (the rightmost node of every level), ordered from the root's level downward.
Return the result as two lists `[left_view, right_view]`.
Implement and reason about **two** approaches:
1. **BFS (level-order):** traverse level by level; the first node dequeued at each level is the left-view node and the last is the right-view node.
2. **DFS (depth tracking):** recurse carrying the current depth; for the left view, visit left child first and record a node only when its depth is first reached; for the right view, visit right child first and record a node only when its depth is first reached.
Both produce identical output. The reference solution below uses BFS.
**Examples**
- `[1,2,3,4,5,null,6]` (root 1; children 2,3; 2's children 4,5; 3's right child 6) -> left view `[1,2,4]`, right view `[1,3,6]`.
- `[]` (empty tree) -> `[[], []]`.
- `[7]` (single node) -> left `[7]`, right `[7]`.
- `[1,2,null,3,null,4]` (left-skewed) -> left `[1,2,3,4]`, right `[1,2,3,4]` (one node per level, so both views match).
**Input encoding.** The tree is a single argument: an array in level order. Each non-null entry is a node value; `null`/`None` marks an absent child. Children of a `null` entry are not listed.
Constraints
- 0 <= number of nodes <= 10^4
- Node values fit in a 32-bit signed integer
- Tree is given in level order with null/None markers; children of a null entry are omitted
- An empty tree returns two empty lists
Examples
Input: ([1, 2, 3, 4, 5, None, 6],)
Expected Output: ([1, 2, 4], [1, 3, 6])
Explanation: Balanced-ish tree: level 0 -> [1], level 1 -> [2,3], level 2 -> [4,5,6]. Leftmost per level = 1,2,4; rightmost = 1,3,6.
Input: ([],)
Expected Output: ([], [])
Explanation: Empty tree: both views are empty.
Hints
- BFS: process the tree one level at a time. The first node you pop for a level is its left-view node; the last is its right-view node.
- DFS: recurse with the current depth. For the left view, recurse into the left child before the right and append a node's value only the first time you reach a given depth (len(view) == depth). For the right view, recurse right-first.
- Both views always have the same length — exactly the height of the tree — because every level contributes exactly one node to each view.
- Watch the edge cases: an empty tree yields two empty lists, and any skewed tree yields identical left and right views (one node per level).