Minimum Absolute Difference in BST
Given the root of a BST, return the minimum absolute difference between the values of any two different nodes in the tree. Use the property that in-order traversal of a BST is sorted.
Why Interviewers Ask This
Uber asks this question to evaluate a candidate's ability to leverage fundamental data structure properties for optimization. Specifically, they assess whether you recognize that an in-order traversal of a Binary Search Tree yields a sorted sequence. This tests your capacity to reduce a naive O(N^2) comparison problem to an efficient O(N) linear scan by utilizing the inherent sorted nature of BSTs rather than brute-forcing all pairs.
How to Answer This Question
1. Clarify the constraints: Confirm if the tree can be empty or contain duplicates, and ask about the expected time complexity. 2. Identify the core property: Explicitly state that an in-order traversal visits nodes in ascending order, meaning the minimum difference must exist between adjacent elements in this sequence. 3. Propose the optimized strategy: Reject comparing every node with every other node. Instead, suggest tracking the previous node visited during the traversal and calculating the absolute difference between the current and previous values. 4. Implement iteratively or recursively: Choose a method (like Morris traversal or simple recursion) to avoid stack overflow risks on deep trees, which Uber often scrutinizes for robustness. 5. Analyze complexity: Conclude by confirming O(N) time complexity as you visit each node once, and O(H) space complexity where H is the tree height for the call stack.
Key Points to Cover
- Explicitly identifying that in-order traversal creates a sorted array
- Reducing the problem from O(N^2) to O(N) by only checking adjacent elements
- Demonstrating awareness of space complexity regarding recursion depth
- Handling edge cases like single-node trees or null inputs correctly
- Clearly articulating the logic flow without writing code immediately
Sample Answer
To solve this efficiently, I first recognize that brute-forcing all pairs would result in O(N^2) time, which is unnecessary given the BST properties. Since an in-order traversal of a BST produces a strictly sorted sequence of values, the minimum absolute difference must occur between two adjacent nodes in this sorted order. Therefore, we only need to compare each node with its immediate predecessor during the traversal.
I would implement this using a recursive in-order approach. I'll maintain a global variable to track the 'previous' node value seen so far, initialized to null. As the recursion visits each node, I calculate the difference between the current node's value and the previous one. If a previous value exists, I update my running minimum difference if this new gap is smaller. Then, I update the previous value to the current node's value before moving to the right subtree.
For example, if the tree contains [4, 2, 6, 1, 3], the in-order traversal yields [1, 2, 3, 4, 6]. We compare 2-1=1, 3-2=1, 4-3=1, and 6-4=2. The minimum is clearly 1. This approach ensures we visit every node exactly once, achieving O(N) time complexity. The space complexity is O(H), where H is the height of the tree, accounting for the recursion stack. This solution is optimal and handles edge cases like single-node trees gracefully by returning infinity or handling them via early checks.
Common Mistakes to Avoid
- Attempting to compare every node with every other node, leading to inefficient O(N^2) solutions
- Forgetting to initialize the 'previous' node tracker correctly, causing incorrect calculations on the first few nodes
- Ignoring the sorted property of BSTs and treating it as a generic binary tree requiring full pairwise comparison
- Overlooking edge cases such as trees with only one node or negative integer values
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.