← Amazon Interview Insights

Amazon·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Amazon SWE interview with a tree problem that looks straightforward until you actually sit down to code it.

Questions Asked (1)

Q1

Given a binary tree, print the nodes visible from the top view, ordered from left to right.

Algorithms & Data Structures
Author's notes

I knew what a top view was conceptually but translating that into code took me longer than it should have.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a level-order traversal (BFS) while tracking each node's horizontal distance from the root. For each horizontal distance, record the first node encountered, then output the recorded nodes sorted by horizontal distance from left to right.

Pro tip: Clarify with the interviewer whether the tree can be empty or have duplicate values, and mention that the top view is essentially the set of nodes that are not obscured by any other node when viewed from above. This shows attention to edge cases and definition precision.

1. Clarify the problem and edge cases

Confirm the definition of 'top view' and ask about empty tree, single node, and duplicate values. Discuss expected output format.

2. Choose the right traversal and data structures

Select BFS (level-order) to ensure topmost nodes are processed first. Use a hash map to store the first node seen at each horizontal distance, and a queue to process nodes with their distances.

3. Implement the BFS with horizontal distance tracking

Start with root at distance 0. For each node, if its distance is not in the map, add it. Then enqueue left child with distance-1 and right child with distance+1.

4. Collect and sort results

After traversal, extract the nodes from the map and sort them by horizontal distance (ascending) to get left-to-right order.

5. Analyze complexity and test

State time complexity O(n log n) due to sorting (or O(n) if using a TreeMap), space O(n). Walk through a small example to verify correctness.

Key Points to Mention

  • Horizontal distance concept: root at 0, left child -1, right child +1.
  • BFS ensures nodes at higher levels are processed before lower ones, so first occurrence at a distance is the topmost.
  • Using a hash map to store the first node per distance, then sorting keys for output.
  • Time complexity: O(n log n) with sorting, or O(n) if using a balanced BST (e.g., TreeMap) for ordered distances.
  • Space complexity: O(n) for the queue and map.
  • Edge cases: empty tree returns empty list; single node returns that node; nodes with same horizontal distance but different levels.

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