Java O(n) Time Inorder Traversal Solution


  • 13

    Since this is a BST, the inorder traversal of its nodes results in a sorted list of values. Thus, the minimum absolute difference must occur in any adjacently traversed nodes. I use the global variable "prev" to keep track of each node's inorder predecessor.

    public class Solution {
        
        int minDiff = Integer.MAX_VALUE;
        TreeNode prev;
        
        public int getMinimumDifference(TreeNode root) {
            inorder(root);
            return minDiff;
        }
        
        public void inorder(TreeNode root) {
            if (root == null) return;
            inorder(root.left);
            if (prev != null) minDiff = Math.min(minDiff, root.val - prev.val);
            prev = root;
            inorder(root.right);
        }
    
    }
    

  • 1
    J

    @compton_scatter clean af


  • 3

    @compton_scatter global variables are generally discouraged. It's probably worth passing mutable values through your stackframes to keep track of a minimum. Here's my implementation:

        public int getMinimumDifference(TreeNode root) {
        	List<Integer> prev = new ArrayList<>(); // contains at most 1 value
        	int[] min = new int[]{Integer.MAX_VALUE};
        	inorder(root, prev, min);
        	return min[0];
        }
        
        private void inorder(TreeNode root, List<Integer> prev, int[] min) {
        	if (root == null) return;
        	
        	inorder(root.left, prev, min);
        	if (prev.isEmpty()) {
        		prev.add(root.val);
        	} else {
        		min[0] = Math.min(min[0], Math.abs(root.val - prev.get(0)));
        		prev.set(0, root.val);
        	}
        	inorder(root.right, prev, min);    	
        }
    

  • 1
    M

    @schumpeter passing a wrapped class is better in my opinion. Much cleaner code,

    class WrapInt{
        int value;
    }

  • 1

    @minhhoangtcu Indeed, hijacking a mutable array to emulate pass-by-reference reeks of a recovering C++ programmer (guilty as charged ;) )


  • 0
    S

    Thanks for your sharing!! But I have a question, how do you calculate the time complexity. Because the inorder method is recursive.


  • 0
    J

    @spoiledpiggy_js For binary tree traversal, time complexity is O(n), since in this example you're hitting each node


Log in to reply
 

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