How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

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.

Input: ([7],)

Expected Output: ([7], [7])

Explanation: Single node: it is both the leftmost and rightmost node of its only level.

Input: ([1, 2, None, 3, None, 4],)

Expected Output: ([1, 2, 3, 4], [1, 2, 3, 4])

Explanation: Left-skewed chain 1->2->3->4. Each level has exactly one node, so left and right views are identical.

Input: ([1, None, 2, None, 3],)

Expected Output: ([1, 2, 3], [1, 2, 3])

Explanation: Right-skewed chain 1->2->3. One node per level, so both views match.

Input: ([1, 2, 3],)

Expected Output: ([1, 2], [1, 3])

Explanation: Root with two children: level 0 -> [1], level 1 -> [2,3]. Left view 1,2; right view 1,3.

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).

Quick Overview

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.