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)


Log in to reply
 

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