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.

Produce asymmetric side views of a binary tree

Quick Overview

Produce asymmetric side views of a binary tree evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given a binary tree, output two sequences: ( 1) Left-bottom-up view: for each depth, the first node visible when viewing the tree from the left side, listed from deepest level up to the root; ( 2) Right-top-down view: for each depth, the first node visible when viewing from the right side, listed from root down to the deepest level. Define visibility as the first node encountered at each depth when traversed from the respective side. Return both sequences. Design an O(n) time solution using O(h) extra space (h = tree height) and describe both DFS and BFS approaches.

Quick Answer: Produce asymmetric side views of a binary tree evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given a binary tree, produce two depth-indexed boundary sequences: 1. **Left-bottom-up view** — for each depth, the first node visible when looking at the tree from the LEFT side (the leftmost node at that depth), listed from the DEEPEST level up to the root. 2. **Right-top-down view** — for each depth, the first node visible when looking from the RIGHT side (the rightmost node at that depth), listed from the ROOT down to the deepest level. Visibility is defined as the first node encountered at each depth when traversed from the respective side. Return both sequences (as `[left_bottom_up, right_top_down]`). **Input encoding.** The tree is given as an array using complete-tree index layout: the node at index `i` has its left child at index `2*i + 1` and its right child at index `2*i + 2`; a missing node is `null`/`None`. Index 0 is the root. An empty array means an empty tree. Aim for O(n) time and O(h) extra space (h = tree height) with the DFS approach, and be ready to describe the BFS alternative.

Constraints

0 <= number of nodes <= 10^4
Node values fit in a 32-bit signed integer
Input is an index-based array: child of i at 2*i+1 (left) and 2*i+2 (right); absent node = null/None
An empty array represents an empty tree and must return [[], []]

Examples

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

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

Explanation: Perfect tree of height 2. Left view by depth = {0:1, 1:2, 2:4}; emitted deepest->root => [4,2,1]. Right view by depth = {0:1, 1:3, 2:7}; emitted root->deepest => [1,3,7].

Input: ([1],)

Expected Output: [[1], [1]]

Explanation: Single node: both side views are just the root at depth 0, so both sequences are [1].

Input: ([],)

Expected Output: [[], []]

Explanation: Empty tree: both sequences are empty.

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

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

Explanation: Depth 2 has only the right child of node 3 (index 6 = 7). Left view depth 2 falls through to that single deepest node 7, so left-bottom-up = [7,2,1]; right view = [1,3,7].

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

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

Explanation: Two levels. Left view {0:1,1:2} -> deepest-up [2,1]; right view {0:1,1:3} -> root-down [1,3].

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

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

Explanation: Left-only chain: index 0=1, index 1=2 (left of root), index 3=4 (left of node 2). Both side views collapse to the single node at each depth: depth0=1, depth1=2, depth2=4. Left-bottom-up=[4,2,1], right-top-down=[1,2,4].

Hints

For each side you only need the FIRST node encountered at every depth. Track a depth -> value map and write a depth only the first time you reach it.
Control which side is 'first' purely by traversal order: for the left view recurse left-child-then-right; for the right view recurse right-child-then-left. The recursion plus 'write-on-first-visit' guarantees the leftmost/rightmost node wins.
The two requested orderings differ only in how you read the same per-depth data: left view is emitted from the deepest depth up to 0, right view from 0 down to the deepest depth.
BFS alternative: do a level-order traversal; the first node dequeued at each level is the left view and the last is the right view. Same O(n), but O(w) queue space instead of O(h).

Quick Overview