Find a cousin in an array

/*
Given the binary Tree and the two nodes say ‘a’ and ‘b’, determine whether the two nodes are cousins of each other or not.

Two nodes are cousins of each other if they are at same level and have different parents.

Example

     6
   /   \
  3     5
 / \   / \
7   8 1   3
Say two node be 7 and 1, result is TRUE.
Say two nodes are 3 and 5, result is FALSE.
Say two nodes are 7 and 5, result is FALSE.
*/

/*Analysis:
The problem can be approached in two steps. 1. find the parent of both target node. 2. check if they are the same? -> if so return false. If they are in the same level -> true. if in different level -> false;
*/

public class solution {
    private TreeNode findParent(TreeNode root, int target) { //return a reference to the parent of the target
        if (root.left == null && root.right == null) // if hit the root
            return null;
        TreeNode left = null;
        TreeNode right = null;
        if (root.left != null) {
            if (root.left.val == target) // find the target in the left child
                return root;
            left = findParent(root.left, target);
        }
        if (root.right != null) {
            if (root.right.val == target)
                return root;
            right = findParent(root.right, target);
        }
        if (left != null)
            return left;
        return right;
    }
    
    private int findLevel(TreeNode root, TreeNode target) {
        if (root == null)
            return -1;
        if (root == target)
            return 0;
        int left = findLevel(root.left, target);
        int right = findLevel(root.right, target);
        if (left != -1)
            return left + 1;
        if (right != -1)
            return right + 1;
        return -1; 
    }    
    
    public boolean isCousin(TreeNode root, int n1, int n2) {
        TreeNode p1 = findParent(root, n1);
        TreeNode p2 = findParent(root, n2);
        if (p1 == null || p2 == null || p1 == p2)
            return false;
        return findLevel(root, p1) == findLevel(root, p2);
    }
}

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