Uber·Software Engineer·Technical Phone Screen·Senior

Senior

May 2026

Summary

Uber SWE interview with a tree traversal problem that looked like a standard BFS question until it wasn't. The twist on visibility and directionality took me a minute to even parse correctly.

Questions Asked (1)

Given a rooted n-ary tree where each node has an ordered list of children, simulate a traversal that starts at the bottom-left, moves up to the root collecting the leftmost visible node at each depth, then continues downward to the bottom-right collecting the rightmost visible node at each depth. Return these as a single sequence with no duplicates. Analyze time and space complexity, write pseudocode, and handle edge cases like a single node or a heavily skewed tree.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I spent the first few minutes just trying to understand what 'visible' meant here.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the traversal definition and edge cases, then design an algorithm that computes the leftmost visible nodes from bottom-left to root and the rightmost visible nodes from root to bottom-right, merging them without duplicates. Use depth-first search to collect nodes at each depth, ensuring O(n) time and O(h) space, and analyze complexity.

Pro tip: Explicitly discuss how you handle the root node to avoid duplication, and mention that the traversal order depends on the definition of 'visible'—confirm with the interviewer if it means the first/last child at each depth.

1. Clarify the problem and edge cases

Restate the traversal in your own words, ask clarifying questions about 'visible' nodes, and identify edge cases like single node, skewed tree, and duplicate handling.

2. Design the algorithm

Plan a two-phase approach: first, traverse from bottom-left to root collecting leftmost nodes per depth; second, traverse from root to bottom-right collecting rightmost nodes per depth, skipping the root in the second phase.

3. Write pseudocode

Implement a DFS that records the first node encountered at each depth for the left side, and another DFS that records the last node encountered at each depth for the right side, then concatenate the results.

4. Analyze complexity

State that the algorithm visits each node once, so time complexity is O(n), and space complexity is O(h) for recursion stack plus O(h) for storing the boundary nodes, where h is the tree height.

5. Test with examples

Walk through a small example and edge cases to verify correctness, ensuring no duplicates and proper ordering.

Key Points to Mention

Definition of 'leftmost visible' and 'rightmost visible' nodes at each depth.
Handling the root node to avoid duplication in the final sequence.
Time complexity O(n) and space complexity O(h) with justification.
Edge cases: single node, skewed tree (left or right), and empty tree.
Use of depth-first search to collect boundary nodes efficiently.
Order of traversal: bottom-left to root, then root to bottom-right.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.