Code Destine

Problem Statement

You have given a binary search tree, find out the minimum difference between the values of any two nodes in the tree.

Example 

Difference between node 16 & 17, 17 & 18 is minimum in above binary search tree. So result is 1.  

Algorithm 

InOrder traversal of binary search tree returns the list of node values in ascending sorted order. During inorder traversal of BST, we can calculate the difference between two adjacent nodes value and can save the minimum value in the temporary variable (result).

Program 

public class MinDiffBST {

	public static void main(String[] args) {
		
		MinDiffBST pot = new MinDiffBST();
		
		TreeNode node = new TreeNode(15);
		node.left = new TreeNode(9);
		node.right = new TreeNode(20);		
		
		node.left.left = new TreeNode(2);
		node.left.right = new TreeNode(11);	
		
		TreeNode node1 = new TreeNode(17);
		TreeNode node2 = new TreeNode(22);
		
		node.right.left = node1;
		node.right.right = node2;	
		
		node1.left = new TreeNode(16);
		node1.right = new TreeNode(18);
		
		node2.right = new TreeNode(25);
		
		int result = pot.getMinimumDifference(node);
		System.out.println(result);
	}
	
	private Integer previous = null;
    private int min = Integer.MAX_VALUE;
    
    public int getMinimumDifference(TreeNode root) {        
        inOrder(root);
        return min;
    }
    
    public void inOrder(TreeNode node){
        
        if(node == null) return;
        
        inOrder(node.left);
         
        if(previous != null){
            if(min > node.val - previous){
                min = node.val - previous;
            }
        }                      
        previous = node.val;
        
        inOrder(node.right);
    }	
	
	public static class TreeNode {		
		int val;
		TreeNode left;
		TreeNode right;
		
		TreeNode(int x) {
			val = x;
		}
	}	
}

Result

1

Similar Post

1. PreOrder Traversal of Tree
2. Average of Levels in Binary Tree
3. InOrder Traversal of Tree

That’s all for Minimum Distance Between BST Nodes in Java, If you liked it, please share your thoughts in a comments section and share it with others too.