Check if two nodes are cousins in a Binary Tree

Question

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.

Looking for code review, optimizations and best practices.

public final class CheckCousins {
 private TreeNode root;
 public CheckCousins(List<Integer> items) {
 create(items);
 }
 private void create (List<Integer> items) {
 if (items.size() == 0) {
 throw new IllegalArgumentException("There should atlease be single item in the tree");
 }
 root = new TreeNode(items.get(0));
 final Queue<TreeNode> queue = new LinkedList<TreeNode>();
 queue.add(root);
 final int half = items.size() / 2;
 for (int i = 0; i < half; i++) {
 if (items.get(i) != null) {
 final TreeNode current = queue.poll();
 final int left = 2 * i + 1;
 final int right = 2 * i + 2;
 if (items.get(left) != null) {
 current.left = new TreeNode(items.get(left));
 queue.add(current.left);
 }
 if (right < items.size() && items.get(right) != null) {
 current.right = new TreeNode(items.get(right));
 queue.add(current.right);
 }
 }
 }
 }
 private static class TreeNode {
 private TreeNode left;
 private int item;
 private TreeNode right;
 TreeNode(int item) {
 this.item = item;
 }
 }
 public boolean isCousin(int x, int y) {
 List<NodeData> nodeDatas = new ArrayList<>();
 isCousins(null, root, x, y, 0, nodeDatas);
 if (nodeDatas.size() < 2) return false;
 NodeData nd1 = nodeDatas.get(0);
 NodeData nd2 = nodeDatas.get(1);
 return nd1.depth == nd2.depth && nd1.parent != nd2.parent;
 }
 private static class NodeData {
 private TreeNode parent;
 private int depth;
 public NodeData(TreeNode parent, int depth) {
 this.parent = parent;
 this.depth = depth;
 }
 }
 private void isCousins(TreeNode parent, TreeNode node, int x, int y, int level, List<NodeData> nodeDatas) {
 if (nodeDatas.size() == 2) return;
 if (node == null) {
 return;
 }
 if (node.item == x || node.item == y) {
 nodeDatas.add(new NodeData(parent, level));
 return;
 }
 isCousins(node, node.left, x, y, level + 1, nodeDatas);
 isCousins(node, node.right, x, y, level + 1, nodeDatas);
 }
}
public class CheckCousinsTest {
 @Test
 public void testIncompleteTree() {
 CheckCousins cs1 = new CheckCousins(Arrays.asList(1, 2, 3, 4, null, null, 7));
 assertTrue(cs1.isCousin(4, 7));
 }
 @Test
 public void testCompleteBinaryTreeSuccess() {
 CheckCousins cs2 = new CheckCousins(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
 assertTrue(cs2.isCousin(4, 7));
 assertTrue(cs2.isCousin(4, 6));
 assertTrue(cs2.isCousin(5, 6));
 assertTrue(cs2.isCousin(5, 7));
 }
 @Test
 public void testCompleteBinaryTreeFailure() {
 CheckCousins cs2 = new CheckCousins(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
 assertFalse(cs2.isCousin(4, 4));
 assertFalse(cs2.isCousin(4, 5));
 assertFalse(cs2.isCousin(6, 7));
 assertFalse(cs2.isCousin(2, 3));
 assertFalse(cs2.isCousin(2, 1));
 }
}

• abuzittin gillifirca: You have to be given some a priori tree implementation, as indicated by 'Given the binary Tree and the two nodes' clause. Otherwise you don't have to implement a tree at all, use integer pairs (m,n) to denote nodes, where m is level and n is the path from root aligned right (0 left, 1 right branch). Then answer would be boolean isCousin = (m1 == m2) && (n1 - n2 > 1);

Answer 1

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

Are we cousins? Normally, I'd say "no", but according to your definition, it's quite possible. Never mind, nice to meet you.

What I dislike most is that you're using both a TreeNode and an index-based tree embedded in an array. I guess, the array serves the initialization only, but I'm not very sure. Unless the initialization is part of task, move it to a separate class.

Your TreeNode-based structure is pretty inefficient for this kind of test. You could do much better with a

class MyTreeNode {
 private int item;
 private MyTreeNode parent;
 private int depth;
}

where the depth only allows you to say "NO" fast.

The whole program would be like

areCousins(MyTreeNode a, MyTreeNode b) {
 return a.depth == b.depth && a.parent != b.parent;
}

just like you wrote above. Without the parent pointers, things get much more complicated. It looks like you did it right, although I struggled with your void isCousins for a while. The is prefix suggest a boolean and you're using a List where a two-member container would fit better.

Because of this, your program fails for trees containing a given node twice like

CheckCousins cs1 = new CheckCousins(Arrays.asList(1, 2, 3, 4, 5, 4, 5));
assertTrue(cs1.isCousin(4, -1));

Not tested, but I guess it fills nodeDatas with the two 4s and you're out of luck.

• abuzittin gillifirca: Are we cousins? You definitely are! You are n th cousins m removed, n~10000, m~1000, where '~' denotes order of magnitude. Only improbable, nonetheless totally possible, bit is m=0 requirement.
• maaartinus: @abuzittingillifirca And given that we're probably multi-cousins, the probability of finding a path having m=0 raises. Wikipedia says However in common parlance, "cousin" normally specifically means "first cousin". and so do I.
• JavaDeveloper: @maaartinus its an interview question - parent ptr is not allowed on purpose - make code more complicated for interviewee