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


  • 9

    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) {
        helper(root,Long.MIN_VALUE,Long.MAX_VALUE);
        return (int)minDiff;
    }
    private void helper(TreeNode curr, long lb, long rb){
        if(curr==null) return;
        if(lb!=Long.MIN_VALUE){
            minDiff = Math.min(minDiff,curr.val - lb);
        }
        if(rb!=Long.MAX_VALUE){
        minDiff = Math.min(minDiff,rb - curr.val);
        }
        helper(curr.left,lb,curr.val);
        helper(curr.right,curr.val,rb);
    }

  • 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
    S

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


  • 0
    S
    This post is deleted!

  • 0

    @simonzheng1234
    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

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


Log in to reply
 

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