Check if Two Trees are Identical

Problem:
Given two binary trees, write a function to check if they are equal or not.

Solution:
Two binary trees are considered equal if they are structurally identical andthe nodes have the same value.

public boolean isSameTree(TreeNode p, TreeNode q) 
{
	if(p==null && q==null)
	{
		return true;
	}
	else if(p==null || q==null)
	{	
		return false;
	}
	else
	{
		return (p.val == q.val && 
				isSameTree(p.left,q.left) && 
				isSameTree(p.right,q.right));
	}
}

Time Complexity: O(N), Where N is number of nodes in a tree.

This article is contributed by Vishwas Garg. You can also contribute by writing and mail it to us: [email protected]

One Thought on “Check if Two Trees are Identical

  1. Simple and elegant recursive solution.
    I am loving it :)

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation