Same Tree

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

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

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        /*Base case 1: p and q are null*/
        if (p == null || q == null) {
            if (p == null && q == null)
                return true; 
            else 
                return false;
        } 
        
        /*Base case 2: p or q are roots*/
        if ((p.left == null) && (p.right == null)) {
            if (q.left == null && q.right == null) {
                if (p.val == q.val) 
                    return true;
                else
                    return false; 
            }
            return false;
        }
        
        /*General case: compare the values of two input nodes*/
        if (p.val != q.val) 
            return false;
        
        return  (isSameTree(p.left, q.left) && isSameTree(p.right, q.right)); 
        
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s