Minimum Distance Between BST Nodes


  • 0

    Click here to see the full article post


  • 0
    C

    For approach #1, if you do an in-order traversal of the tree (given it's a BST) you remove the need to sort the nodes. This approach takes it down to O(N) runtime O(N) space.


  • 0
    S

    I think that question should be renamed to "Minimum Difference Between BST Nodes".


  • 0
    I
    public int minDiffInBST(TreeNode root) {
            if(root == null ){
                return Integer.MAX_VALUE;
            }
            
            ArrayList<Integer> l = new ArrayList<>();
            getInorder(root,l);
            int diff = Integer.MAX_VALUE;
            for(int i=1;i<l.size();i++){
                diff = Math.min(diff,Math.abs(l.get(i-1) - l.get(i)));
            }
            return diff;
        }
        public void getInorder(TreeNode root,ArrayList<Integer> l) {
            if(root!=null){
                getInorder(root.left,l);
                l.add(root.val);
                getInorder(root.right,l);
            }
        }
    

  • 0
    P

    In approach 1, why are we required to sort? Just the inorder traversal of the entire tree should yield the sorted order. So the time complexity can be reduced to O(n)


  • 0
    J

    How come for [4,2,6,1,3,null,null] the expected answer is 1, while for [2, 4, 6, 1, 3, null, null] the expected is -1?
    Is there an order requirement for the division?


  • 0
    L

    Approach 1 is wrong because adjacent elements will not be necessary adjacent nodes in the tree i.e [2,1,4,0,6,3,5]
    And use in-order traversal is dumb because of this fact.


  • 0
    L

    Approach2 is correct and really smart. Set the value of None node to inf.


  • 0
    P

    @lqian-udel.edu It is not a requirement in the question that the minimum difference between two nodes has to be between two adjacent nodes. The question specifies "any" two different nodes. So, in order approach is not at all a dumb approach.


Log in to reply
 

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