Produce asymmetric side views of a binary tree
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: This question evaluates proficiency with binary tree data structures and traversal strategies, specifically DFS and BFS, along with the ability to derive asymmetric left-bottom-up and right-top-down views while reasoning about time and space complexity.