Katkat
Back

Produce asymmetric side views of a binary tree

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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