Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Interviewed for a software engineering role at Uber, got a BST problem that seemed straightforward until the follow-up hit. The follow-up is where things got interesting and honestly where I felt underprepared.

Questions Asked (1)

Given the root of a binary search tree and an integer k, return the k-th smallest value in the tree (1-indexed).

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

In-order traversal, pretty textbook.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use an in-order traversal of the BST to visit nodes in ascending order, counting until you reach the k-th node. Alternatively, if the tree is static and multiple queries are expected, augment each node with the size of its left subtree to enable O(log n) queries. Discuss the trade-offs between simplicity and efficiency based on the problem constraints.

Pro tip: Mention that the in-order traversal can be done iteratively with a stack to avoid recursion depth issues, and that the follow-up often involves handling frequent k-th smallest queries, where an augmented BST is preferred.

1. Clarify requirements and constraints

Ask about the tree size, whether k is guaranteed valid, and if the tree will be modified or if multiple queries will be made. This determines whether a simple traversal or an augmented data structure is appropriate.

2. Propose in-order traversal solution

Explain that an in-order traversal of a BST yields sorted order, so you can traverse and decrement k until it reaches zero, returning the current node's value. This is O(n) time and O(h) space for recursion or stack.

3. Optimize with augmented BST (if needed)

If multiple queries are expected, suggest augmenting each node with the size of its left subtree. Then, at each node, compare k with the left subtree size to decide whether to go left, return the node, or go right with adjusted k, achieving O(log n) average time.

4. Analyze trade-offs and edge cases

Compare the time and space complexity of both approaches, and discuss edge cases like k=1 (smallest), k=n (largest), skewed trees, and invalid k. Mention that the augmented approach requires extra space per node and updates on insertion/deletion.

5. Implement and test

Write clean code for the chosen approach, using iterative in-order traversal to avoid recursion limits. Test with examples, including a balanced tree and a skewed tree, and verify k=1 and k=n.

Key Points to Mention

In-order traversal of a BST yields nodes in ascending order.
Time complexity: O(n) for traversal, O(log n) for augmented BST (average).
Space complexity: O(h) for recursion/stack, O(n) for augmented tree.
Augmented BST stores subtree sizes to enable efficient k-th smallest queries.
Edge cases: k=1, k=n, invalid k, skewed tree (height n).
Iterative in-order traversal using a stack avoids recursion depth issues.

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