Java No In-order Traverse Solution, just pass upper bound and lower bound

  • 11

    Make use of the property of BST that value of nodes is bounded by their "previous" and "next" node.
    Edit: Thanks to Stefan pointing out a small bug. Previous code would fail when testing [2147483647, 2147483646].
    Now Long.MAX_VALUE/MIN_VALUE is used to mark the INF.

    long minDiff = Long.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
        return (int)minDiff;
    private void helper(TreeNode curr, long lb, long rb){
        if(curr==null) return;
            minDiff = Math.min(minDiff,curr.val - lb);
        minDiff = Math.min(minDiff,rb - curr.val);

  • 4

    I've done something similar, but returning the value instead of having a "global" variable (since that's nicer in Python):

    def getMinimumDifference(self, root):
        def mindiff(root, lo, hi):
            if not root:
                return float('inf')
            return min(root.val - lo,
                       hi - root.val,
                       mindiff(root.left, lo, root.val),
                       mindiff(root.right, root.val, hi))
        return mindiff(root, float('-inf'), float('inf'))

  • 0

    @Nakanu your answer is great, how can you think of this solution and implement it.

  • 0
    This post is deleted!

  • 0

    It is just sort of property of the BST. Since the value of all the nodes of the left subtree is smaller than the current node, the value of the current node is the upper bound of the all the nodes in the left subtree. And for the right subtree, the value of the current node is the lower bound. You can draw a BST and have a look. If you draw a vertical line for 2 nodes, you will find all the nodes between those two lines are bounded by the value of the nodes which you draw the vertical lines.

  • 0

    Just a little bug: It fails for example [2147483647, 2147483646], returning 2147483647 instead of 1.

  • 0

    You are right, Stefan. I think I should use Long.MAX_VALUE here.

  • 0

    Smart idea!

    I think you can use TreeNode to represent a lower bound or an upper bound.

    Here's my C++ version:

    class Solution {
        void preorder(TreeNode* curr, TreeNode* lb, TreeNode* ub, int& min_diff) {
            if (curr == nullptr) return;
            if (lb != nullptr) min_diff = min(min_diff, curr->val - lb->val);
            if (ub != nullptr) min_diff = min(min_diff, ub->val - curr->val);
            preorder(curr->left, lb, curr, min_diff);
            preorder(curr->right, curr, ub, min_diff);
        int getMinimumDifference(TreeNode* root) {
            int min_diff = INT_MAX;
            preorder(root, nullptr, nullptr, min_diff);
            return min_diff;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.