Code Destine

Problem Statement

You have given two binary trees, find out if both trees are same or not. Two binary trees are same, if they are structurally identical and the nodes have same value.

Example 

1)  Above two binary trees are structurally same and their node values are also same.

2)  Above two binary trees are structurally same but their node values are different.

Algorithm 

We can use Depth First Traversal algorithm to solve this problem.

Program 

public class SameTree {

	public static void main(String[] args) {
		
		SameTree same = new SameTree();
		
		TreeNode first = new TreeNode(3);
		first.left = new TreeNode(6);
		first.right = new TreeNode(9);		
		
		TreeNode second = new TreeNode(3);
		second.left = new TreeNode(9);
		second.right = new TreeNode(6);		
		
		boolean result = same.isSameTree(first, second);
		System.out.println(result);
	}
	
	public boolean isSameTree(TreeNode first, TreeNode second) {
        
		if(first == null && second == null){
            return true;
        }        
        
		if((first == null || second == null) || first.val != second.val){
            return false;
        }        
        
		if(!isSameTree(first.left, second.left)){
            return false;
        }
		
        if(!isSameTree(first.right, second.right)){
            return false;
        }
        return true;
    }
	
	public static class TreeNode {		
		int val;
		TreeNode left;
		TreeNode right;
		
		TreeNode(int x) {
			val = x;
		}
	}
}

Result

false

Similar Post

1. Same Tree
2. Sum of all Left Leaves
3. Level Order Traversal of Binary Tree

That’s all for Same tree in Java, If you liked it, please share your thoughts in a comments section and share it with others too.