Simulate views on an n-ary tree

Quick Overview

This question evaluates proficiency in tree traversal and algorithm design for ordered n-ary trees, focusing on identifying visible boundary nodes given child ordering and reasoning about time and space complexity.

Simulate views on an n-ary tree

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given a rooted, ordered n-ary tree (each node has a value and an ordered list of children), simulate an observer who starts at the bottom-left, moves upward to the root level while looking to the right, then continues downward to the bottom-right while looking to the left. At each depth during the upward phase, output the leftmost visible node (the first node encountered at that depth when scanning children left-to-right). During the downward phase, at each depth output the rightmost visible node (the first node encountered at that depth when scanning children right-to-left). Concatenate these into one sequence without duplicates (do not repeat the root if already output). Design an algorithm to compute this sequence for any n-ary tree, analyze time and space complexity, provide pseudocode, and discuss edge cases such as a single-node tree and highly unbalanced trees.

Quick Answer: This question evaluates proficiency in tree traversal and algorithm design for ordered n-ary trees, focusing on identifying visible boundary nodes given child ordering and reasoning about time and space complexity.

|Home/Coding & Algorithms/Uber
Uber logo
Uber
Sep 6, 2025, 12:00 AM
mediumSoftware EngineerTechnical ScreenCoding & Algorithms
5
0

Given a rooted, ordered n-ary tree (each node has a value and an ordered list of children), simulate an observer who starts at the bottom-left, moves upward to the root level while looking to the right, then continues downward to the bottom-right while looking to the left. At each depth during the upward phase, output the leftmost visible node (the first node encountered at that depth when scanning children left-to-right). During the downward phase, at each depth output the rightmost visible node (the first node encountered at that depth when scanning children right-to-left). Concatenate these into one sequence without duplicates (do not repeat the root if already output). Design an algorithm to compute this sequence for any n-ary tree, analyze time and space complexity, provide pseudocode, and discuss edge cases such as a single-node tree and highly unbalanced trees.

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...