Uber·Software Engineer·Technical Phone Screen·Senior

Senior

Jun 2026

Summary

Uber SWE interview that went deep on BST traversal and space complexity. The follow-up question was the whole interview basically, they didn't care much about the initial solution once you got it working.

Questions Asked (1)

You've written iterative and recursive solutions for finding the k-th largest element in a BST. Now describe an approach that uses O(1) extra space. No code needed, but walk through at least three options and compare their trade-offs.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This is where I actually had to think.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints and then present three distinct O(1) space approaches: Morris traversal, parent pointers, and threaded tree. For each, explain the algorithm, analyze time and space complexity, and discuss trade-offs such as mutability, preprocessing, and practical applicability. Conclude with a recommendation based on typical constraints.

Pro tip: Emphasize that while O(1) space is achievable, the constant factors and code complexity often make simpler O(h) solutions preferable in practice; showing this awareness demonstrates engineering maturity.

1. Clarify constraints and assumptions

Ask whether the BST can be modified, if parent pointers exist, and if recursion stack counts as extra space. This sets the stage for valid O(1) solutions.

2. Present Morris traversal approach

Explain how to do an in-order traversal using temporary threaded links to predecessors, achieving O(1) space and O(n) time. Mention that it temporarily modifies the tree but restores it.

3. Present parent pointer approach

If nodes have parent pointers, describe how to perform an in-order traversal without a stack by moving up and down the tree. Note that this requires O(1) space but assumes parent pointers are available.

4. Present threaded tree approach

Explain that if the tree is pre-threaded (with right pointers to successors), an in-order traversal is straightforward and uses O(1) space. Mention that this requires preprocessing and is not suitable for dynamic trees.

5. Compare trade-offs and recommend

Contrast the approaches: Morris is self-contained but modifies tree temporarily; parent pointers require extra field but are simple; threaded tree needs preprocessing. Recommend based on constraints like tree mutability and update frequency.

Key Points to Mention

Morris traversal: O(1) space, O(n) time, temporarily modifies tree, restores it.
Parent pointers: O(1) space, O(n) time, requires parent pointers, no modification.
Threaded tree: O(1) space, O(n) time, requires preprocessing, not for dynamic trees.
Trade-offs: code complexity, constant factors, mutability, preprocessing overhead.
Comparison with O(h) stack-based solutions: often simpler and preferred in practice.
Edge cases: k out of bounds, empty tree, skewed tree performance.

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