Cousins in Binary Tree Solution in C++

Explore More Solutions:

• Java Solution
• Python Solution

Problem Description

Ah, the classic “Cousins in Binary Tree” problem! It’s like a family reunion where you’re trying to figure out if two relatives are actually cousins or just pretending to be. Imagine you’re at a family gathering, and you overhear someone say, “Hey, are you related to that guy over there?” You squint, trying to remember if you’ve ever met that person before. Well, this problem is just like that, but with binary trees instead of awkward family members.

In this problem, you’re given a binary tree and two integers, x and y. Your mission, should you choose to accept it, is to determine if these two integers are cousins. Cousins in this context mean that they are on the same level of the tree but have different parents. So, if you find out that x and y are hanging out on the same level but have different moms and dads, congratulations! You’ve found some cousins!

Code Solution

Copy Code

class Solution {
 public:
  bool isCousins(TreeNode* root, int x, int y) {
    if (root == nullptr)
      return false;

    queue queue{{root}};

    while (!queue.empty()) {
      bool isFindX = false;
      bool isFindY = false;
      for (int i = queue.size(); i > 0; --i) {
        root = queue.front(), queue.pop();
        if (root->val == x)
          isFindX = true;
        else if (root->val == y)
          isFindY = true;
        else if (root->left && root->right) {
          if (root->left->val == x && root->right->val == y)
            return false;
          if (root->left->val == y && root->right->val == x)
            return false;
        }
        if (root->left)
          queue.push(root->left);
        if (root->right)
          queue.push(root->right);
      }
      if (isFindX && isFindY)
        return true;
      else if (isFindX || isFindY)
        return false;
    }

    return false;
  }
};

Approach

The approach taken in this solution is quite straightforward. We use a breadth-first search (BFS) strategy to traverse the binary tree level by level. Here’s a brief rundown of what happens:

1. Initialization: We start by checking if the root is null. If it is, we return false because there’s no tree to work with.
2. Queue Setup: We use a queue to keep track of the nodes we need to explore. We initialize it with the root node.
3. Level Traversal: We enter a loop that continues until the queue is empty. For each level, we check if we can find both x and y.
4. Cousin Check: If we find both x and y at the same level, we return true. If we find one but not the other, we return false. If we find them as siblings (same parent), we also return false.
5. Continue: If we finish checking a level without finding both, we continue to the next level.

Time and Space Complexity

Time Complexity: O(N), where N is the number of nodes in the binary tree. In the worst case, we may need to visit every node.
Space Complexity: O(W), where W is the maximum width of the tree. This is the space required for the queue.

Real-World Example

Imagine you’re at a family reunion, and you spot two cousins, Timmy and Tommy, who are both 10 years old. They’re playing on the same level of the jungle gym, but wait! You notice that they’re both climbing up the same slide, which means they’re not cousins after all—they’re siblings! This is exactly what our code is checking for: are Timmy and Tommy on the same level but have different parents? If yes, they’re cousins!

Similar Problems

• Binary Tree Level Order Traversal