โ† Amazon questions

Populate next pointers in tree and top K frequent strings

Filed under Amazon

Free read 2 of 3

Use a level-order traversal approach. Since we can use the 'next' pointers of the current level to connect the next level, we avoid extra space.

The question

Part 1: Populate 'next' pointers in a binary tree to point to the node to the right at the same level. Part 2: Given a stream of strings, return the top 10 most frequent strings.

Constraints

  • Tree next pointer: O(1) extra space (excluding recursion stack).
  • Top K: Handle large streams where all strings don't fit in memory.
  • Top K: Time complexity should be efficient for frequent updates.

Examples

Input
Tree: [1, 2, 3, 4, 5]
Output
1->null, 2->3->null, 4->5->null
Why
Each node's next pointer connects to the node immediately to its right at the same depth.

Approach

  1. Use a level-order traversal approach. Since we can use the 'next' pointers of the current level to connect the next level, we avoid extra space.

Tips

  • What they are testing: Verify tree connectivity for non-perfect binary trees. For top K, test with a small K and a stream with high frequency variance.
  • Common mistake: Using extra queue space for the tree problem instead of leveraging existing next pointers to traverse levels.

Related Amazon questions

Collected from public candidate posts and coding forums. Updated Nov 2026.