Cousins in binary tree

XXX. Cousins in Binary Tree

Tree

Breadth-First Search

Problem Statement:

Given the root of a binary tree and two integers x and y, return true if the nodes corresponding to x and y are cousins. Two nodes are considered cousins if they are at the same depth in the tree but have different parents.

Algorithm:

1. Use a breadth-first search (BFS) approach to traverse the tree level by level.
2. For each level, check the following:
   • If the children of the current node are x and y, return false as they have the same parent.
   • If x or y is found, update the corresponding flag.
3. If both x and y are found at the same level but not as siblings, return true.
4. If only one of them is found at the end of a level, return false.

Complexity:

Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(w), where w is the maximum width of the tree (queue size in BFS).

Java Implementation:

public boolean isCousins(TreeNode root, int x, int y) {
    Queue q = new LinkedList<>();
    q.add(root);

    boolean foundX = false;
    boolean foundY = false;

    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode curr = q.poll();

            // Check if x and y are children of the same parent
            if (curr.left != null && curr.right != null) {
                if ((curr.left.val == x && curr.right.val == y) || (curr.left.val == y && curr.right.val == x)) 
                    return false;
            }

            if (curr.val == x) foundX = true;
            if (curr.val == y) foundY = true;

            if (curr.left != null) q.add(curr.left);
            if (curr.right != null) q.add(curr.right);
        }

        if (foundX && foundY) return true;
        if (foundX || foundY) return false;
    }

    return false;
}
                

Python Implementation:

from collections import deque

def is_cousins(root, x, y):
    q = deque([root])

    while q:
        size = len(q)
        found_x = found_y = False

        for _ in range(size):
            curr = q.popleft()

            # Check if x and y are children of the same parent
            if curr.left and curr.right:
                if (curr.left.val == x and curr.right.val == y) or (curr.left.val == y and curr.right.val == x):
                    return False

            if curr.val == x:
                found_x = True
            if curr.val == y:
                found_y = True

            if curr.left:
                q.append(curr.left)
            if curr.right:
                q.append(curr.right)

        if found_x and found_y:
            return True
        if found_x or found_y:
            return False

    return False
                

C++ Implementation:

#include 
using namespace std;

bool isCousins(TreeNode* root, int x, int y) {
    queue q;
    q.push(root);

    while (!q.empty()) {
        int size = q.size();
        bool foundX = false, foundY = false;

        for (int i = 0; i < size; i++) {
            TreeNode* curr = q.front();
            q.pop();

            // Check if x and y are children of the same parent
            if (curr->left && curr->right) {
                if ((curr->left->val == x && curr->right->val == y) || (curr->left->val == y && curr->right->val == x))
                    return false;
            }

            if (curr->val == x) foundX = true;
            if (curr->val == y) foundY = true;

            if (curr->left) q.push(curr->left);
            if (curr->right) q.push(curr->right);
        }

        if (foundX && foundY) return true;
        if (foundX || foundY) return false;
    }

    return false;
}