Minimum Distance Between BST Nodes

Easy · Graphs · Explanation and code example

Morris Traversal

How it works

Morris traversal allows us to perform inorder traversal without using a stack or recursion, achieving O(1) extra space. The idea is to temporarily modify the tree by creating links from predecessor nodes back to their successors, allowing us to navigate the tree without additional memory. We traverse the tree, comparing consecutive values as before.

Steps

  1. Initialize cur to the root and prevVal to track the value of the previous node visited.
  2. While cur is not null:
    • If cur has no left child:
      • Process cur (compare with prevVal and update minimum).
      • Update prevVal and move to the right child.
    • Else, find the inorder predecessor (rightmost node in left subtree):
      • If the predecessor's right pointer is null, set it to cur and move left.
      • If the predecessor's right pointer is cur, restore it to null, process cur, update prevVal, and move right.
  3. Return the minimum difference found.

Complexity

  • Time complexity: O(n)
  • Space complexity: O(1) extra space.

Things to watch for

Not Leveraging BST Properties

The most common mistake is treating this as a generic binary tree problem and comparing all pairs of nodes, resulting in O(n^2) time complexity. The BST property guarantees that inorder traversal produces a sorted sequence, so the minimum difference must occur between consecutive elements. Always use inorder traversal to reduce complexity to O(n).

Comparing Non-Adjacent Elements

In a sorted sequence, the minimum difference is always between adjacent elements. Some implementations incorrectly compare non-adjacent pairs or track global minimum/maximum values instead of the previous node, missing the optimal answer or overcomplicating the solution.

Python code example

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        prevVal = res = float("inf")
        cur = root

        while cur:
            if not cur.left:
                if prevVal != float("inf"):
                    res = min(res, cur.val - prevVal)
                prevVal = cur.val
                cur = cur.right
            else:
                prev = cur.left
                while prev.right and prev.right != cur:
                    prev = prev.right

                if not prev.right:
                    prev.right = cur
                    cur = cur.left
                else:
                    prev.right = None
                    if prevVal != float("inf"):
                        res = min(res, cur.val - prevVal)
                    prevVal = cur.val
                    cur = cur.right

        return res

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        int prevVal = INT_MAX, res = INT_MAX;
        TreeNode* cur = root;

        while (cur) {
            if (!cur->left) {
                if (prevVal != INT_MAX) {
                    res = min(res, cur->val - prevVal);
                }
                prevVal = cur->val;
                cur = cur->right;
            } else {
                TreeNode* prev = cur->left;
                while (prev->right && prev->right != cur) {
                    prev = prev->right;
                }

                if (!prev->right) {
                    prev->right = cur;
                    cur = cur->left;
                } else {
                    prev->right = nullptr;
                    if (prevVal != INT_MAX) {
                        res = min(res, cur->val - prevVal);
                    }
                    prevVal = cur->val;
                    cur = cur->right;
                }
            }
        }

        return res;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations