PracHub
QuestionsCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates proficiency in tree data structures and algorithm design, focusing on traversal and boundary extraction in ordered N-ary trees while requiring time and space complexity analysis.

  • medium
  • Uber
  • Coding & Algorithms
  • Software Engineer

Compute outer boundary of an N-ary tree

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given the root of a rooted **N-ary tree**. Each node contains: - An integer value. - An ordered list of children from left to right (0 or more children). Consider all nodes grouped by their depth (root at depth 0, its children at depth 1, etc.). For each depth `d`: - Let **L_d** be the *leftmost* node at depth `d` (the first node at that depth when scanning children from left to right). - Let **R_d** be the *rightmost* node at depth `d` (the last node at that depth when scanning children from left to right). We define the **outer boundary path** of the tree as the sequence of nodes you would "see" when walking around the outside of the tree, starting from the lowest leftmost node, going up to the root, then going down to the lowest rightmost node: 1. Starting from the **maximum depth D** down to `0`, take `L_D, L_{D-1}, ..., L_0` (bottom-left up to the root). 2. Then from depth `1` up to `D`, take `R_1, R_2, ..., R_D` (top-right down to bottom-right), **skipping** `R_d` when `R_d` is the same node as `L_d` to avoid duplicates on levels with only one node. Return the list of node values in this exact order. Assume: - Total number of nodes `n` satisfies `1 <= n <= 10^5`. - Tree height `h` can be up to `n` in the worst case. **Task**: Design an efficient algorithm to compute and return this outer boundary path. Specify the time and space complexity of your approach.

Quick Answer: This question evaluates proficiency in tree data structures and algorithm design, focusing on traversal and boundary extraction in ordered N-ary trees while requiring time and space complexity analysis.

Return boundary values from lowest leftmost node up to root, then down rightmost nodes, skipping duplicates on single-node levels.

Constraints

  • Children are ordered left to right

Examples

Input: ({'val': 1, 'children': [{'val': 2, 'children': [{'val': 5}, {'val': 6}]}, {'val': 3}, {'val': 4, 'children': [{'val': 7}]}]},)

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

Input: ({'val': 1},)

Expected Output: [1]

Input: ({'val': 1, 'children': [{'val': 2, 'children': [{'val': 3}]}]},)

Expected Output: [3, 2, 1]

Hints

  1. Level-order traversal gives leftmost and rightmost node per depth.
Last updated: Jun 27, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Deep Equality of Two Records - Uber (medium)
  • Shortest Path in a Grid with Blocked Cells - Uber (medium)
  • Design and Implement an LRU Cache - Uber (medium)
  • Reconstruct the Alphabet Order of an Alien Language - Uber (medium)
  • Maximize Throughput and Count Trigger Components - Uber (medium)