Minimum Absolute Difference in BST

Minimum Absolute Difference in BST

What is this problem about?

The Minimum Absolute Difference in BST coding problem asks you to find the smallest numerical difference between the values of any two distinct nodes in a Binary Search Tree (BST). Because it is a BST, the tree already possesses a specific structure where for any given node, all values in its left subtree are smaller and all values in its right subtree are larger. This inherent order is the key to solving the problem efficiently without comparing every single pair of nodes, which would be computationally expensive.

Why is this asked in interviews?

This is a classic Minimum Absolute Difference in BST interview question because it tests a candidate's fundamental understanding of tree data structures and their properties. Interviewers at companies like Meta and Google look for your ability to leverage the BST property to optimize a search. It demonstrates whether you can convert a tree problem into a linear problem by using specific traversal techniques, showing your grasp of time and space complexity.

Algorithmic pattern used

The most effective Binary Search Tree interview pattern for this problem is the In-order Traversal (Left -> Root -> Right). When you perform an in-order traversal on a BST, you visit the nodes in a strictly non-decreasing (sorted) order. Once the values are "flattened" into a sorted sequence, the minimum absolute difference must exist between two adjacent elements in that sequence. This reduces the problem from a complex tree search to a simple linear scan of sorted values.

Example explanation

Imagine a BST with a root node 8, a left child 3, and a right child 10.

1. We start our in-order traversal: visit the left subtree of 8, which is 3.
2. 3 has no children, so we record 3.
3. We move back to the root 8 and record it. Current sequence: [3, 8]. Difference is 5.
4. We visit the right child 10. Current sequence: [3, 8, 10].
5. We check the difference between the new element 10 and the previous element 8. The difference is 2.
6. Since 2 is smaller than 5, the minimum absolute difference for this tree is 2.

Common mistakes candidates make

• Comparing non-adjacent nodes: Some candidates try to compare the root with all leaves or use a Breadth-First Search (BFS) which doesn't guarantee sorted order, leading to unnecessary comparisons.
• Not using the BST property: Treating the tree as a regular Binary Tree and sorting all values manually after extraction, which wastes time (O(N log N) instead of O(N)).
• Handling the first node: Forgetting to initialize the "previous" node pointer correctly, which can lead to comparing the first node with a null value or zero incorrectly.

Interview preparation tip

Always remember that an In-order Traversal is your best friend whenever you see a BST problem involving sorted order, ranges, or differences. Practice implementing this traversal both recursively and iteratively, as some interviewers might ask you to avoid recursion to save stack space.