Cousins in Binary Tree LeetCode solution in C++

1
class Solution {
2
 public:
3
  bool isCousins(TreeNode *root, int x, int y) {
4
    if (root->left == NULL || root->right == NULL) return false;
5
    // to store node with parent
6
    queue<pair<TreeNode *, TreeNode *>> q;
7
    // push root
8
    q.push({root, NULL});
9
    // push NULL for level seperation
10
    q.push({NULL, NULL});
11
    // boolean val to know if we found x or y yet during traversal of tree
12
    pair<bool, TreeNode *> foundx = {false, NULL}, foundy = {false, NULL};
13

14
    // start the level order traversal
15
    while (!q.empty()) {
16
      TreeNode *top = q.front().first;
17
      TreeNode *parent = q.front().second;
18
      q.pop();
19

20
      // when a level is completely traversed
21
      if (top == NULL) {
22
        // if we found both x and y and if their parent are not same we found
23
        // cousins
24
        if (foundx.first && foundy.first && foundx.second != foundy.second) return true;
25
        // if one of them found when other not, or when both were found and
26
        // their parent were equal
27
        if (foundx.first || foundy.first) return false;
28
        // push another NULL for further level seperation, if there are any.
29
        if (!q.empty()) q.push({NULL, NULL});
30
      } else {
31
        // find x and y
32
        if (top->val == x) foundx = {true, parent};
33
        if (top->val == y) foundy = {true, parent};
34

35
        // push current node's childs with parent as current node.
36
        if (top->left) q.push({top->left, top});
37
        if (top->right) q.push({top->right, top});
38
      }
39
    }
40
    return false;
41
  }
42
};