Cousins in Binary Tree LeetCode solution in Java

1
/**
2
 * Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode
3
 * right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left,
4
 * TreeNode right) { this.val = val; this.left = left; this.right = right; } }
5
 */
6
class Solution {
7
  public boolean isCousins(TreeNode root, int x, int y) {
8

9
    // If any of x or y is at root, it means they can't be at same depth. Return false.
10
    if (root.val == x || root.val == y) return false;
11

12
    Deque<TreeNode> queue = new LinkedList<>();
13
    queue.offer(root);
14

15
    boolean xFound = false;
16
    boolean yFound = false;
17

18
    int parentX = 0;
19
    int parentY = 0;
20

21
    // Do level-order traversal until x or y is found or queue is empty.
22
    while (!queue.isEmpty() && !xFound && !yFound) {
23

24
      int size = queue.size();
25

26
      // Traverse that level.
27
      while (size-- > 0) {
28
        TreeNode node = queue.poll();
29

30
        // if x or y is found at left/right, save the parent and set the "found" flag to true.
31
        // This flag will break the loop as soon as any one (x or y) is found.
32
        // we don't need to go deeper to find second if it isn't found at this level.
33

34
        if (node.left != null) {
35
          queue.offer(node.left);
36

37
          if (node.left.val == x) {
38
            parentX = node.val;
39
            xFound = true;
40
          }
41
          if (node.left.val == y) {
42
            parentY = node.val;
43
            yFound = true;
44
          }
45
        }
46

47
        if (node.right != null) {
48
          queue.offer(node.right);
49

50
          if (node.right.val == x) {
51
            parentX = node.val;
52
            xFound = true;
53
          }
54
          if (node.right.val == y) {
55
            parentY = node.val;
56
            yFound = true;
57
          }
58
        }
59
      }
60
    }
61
    return xFound && yFound && parentX != parentY;
62
  }
63
}