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 Technical Screen rounds at Meta.

What role is this question designed for?

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

Compute left and right views once | Meta Coding Question

Quick Overview

This question evaluates understanding of binary tree traversal, depth tracking, and view computation for left and right perspectives, plus the ability to implement a concurrent single-pass traversal while handling edge cases such as empty trees and duplicate keys.

Compute left and right views once

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given the root of a binary search tree, output two lists: the nodes visible from the left side and the nodes visible from the right side, from top to bottom. Implement a single-pass traversal that computes both views concurrently. Discuss iterative vs. recursive strategies, how you track depth and first/last-at-depth nodes, and analyze time/space complexity. Handle empty trees and trees with duplicate keys.

Quick Answer: This question evaluates understanding of binary tree traversal, depth tracking, and view computation for left and right perspectives, plus the ability to implement a concurrent single-pass traversal while handling edge cases such as empty trees and duplicate keys.

Given the root of a binary tree, return two lists: the **left view** (the first node seen at each depth, scanning top to bottom) and the **right view** (the last node seen at each depth). Compute BOTH views in a single traversal. The tree is provided as a LeetCode-style level-order array `level_order`, where each element is a node value or `null` (`None`) to denote a missing child. Reconstruct the tree, then traverse it once. Return the answer as a list of two lists: `[left_view, right_view]`. A single level-order BFS works naturally: at each level the first dequeued node is on the left edge and the last is on the right edge. Empty trees return `[[], []]`. Duplicate keys are allowed and are emitted by value (a single-node level contributes its value to both views). Example: for `[1, 2, 3, 4, null, null, 5]` the left view is `[1, 2, 4]` and the right view is `[1, 3, 5]`, so the answer is `[[1, 2, 4], [1, 3, 5]]`.

Constraints

0 <= number of nodes <= 10^4
Node values fit in a 32-bit signed integer
Duplicate node values are allowed
The tree may be empty (level_order is empty or begins with None)
Must compute both views in a single traversal of the tree

Examples

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

Expected Output: [[1, 2, 4], [1, 3, 5]]

Explanation: Levels: [1], [2,3], [4,5]. Left view takes the first of each level (1,2,4); right view takes the last (1,3,5).

Input: ([],)

Expected Output: [[], []]

Explanation: Empty tree: both views are empty.

Input: ([7],)

Expected Output: [[7], [7]]

Explanation: Single node is simultaneously the leftmost and rightmost at its level, so it appears in both views.

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

Expected Output: [[1, 2, 5], [1, 3, 4]]

Explanation: Levels: [1], [2,3], [5,4]. Node 5 is 2's right child and is leftmost at depth 2; node 4 is 3's right child and is rightmost at depth 2.

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

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

Explanation: A left-skewed chain: each level has exactly one node, so the left and right views coincide.

Input: ([5, 5, 5, 5, None, None, 5],)

Expected Output: [[5, 5, 5], [5, 5, 5]]

Explanation: Duplicate keys: views are emitted by value. Levels [5],[5,5],[5,5] give first-of-level [5,5,5] and last-of-level [5,5,5].

Hints

A level-order BFS gives you the views for free: at each level, the first node you dequeue is the leftmost (left view) and the last is the rightmost (right view).
Snapshot the queue size at the start of each level so you know which dequeue index is first (i == 0) and which is last (i == n-1).
When the tree is a single chain (only-left or only-right children), every level has exactly one node, so the left and right views are identical.
A recursive DFS also works: pass the current depth, and for the left view record the first value reached at each new depth (preorder, left-first); for the right view record the first value reached visiting right-first.

Quick Overview