# Cousins in Binary Tree
**Difficulty:** EASY
[External](https://leetcode.com/problems/cousins-in-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/cousins-in-binary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Tekion](https://scaleengineer.com/companies/tekion)
---
## Problem
Given the `root` of a binary tree with unique values and the values of two different nodes of the tree `x` and `y`, return `true` _if the nodes corresponding to the values_ `x` _and_ `y` _in the tree are **cousins**, or_ `false` _otherwise._

Two nodes of a binary tree are **cousins** if they have the same depth with different parents.

Note that in a binary tree, the root node is at the depth `0`, and children of each depth `k` node are at the depth `k + 1`.

**Example 1:**

![](https://assets.glich.co/dsa/cousins-in-binary-tree/image0.png) 

**Input:** root = [1,2,3,4], x = 4, y = 3
**Output:** false

**Example 2:**

![](https://assets.glich.co/dsa/cousins-in-binary-tree/image1.png) 

**Input:** root = [1,2,3,null,4,null,5], x = 5, y = 4
**Output:** true

**Example 3:**

![](https://assets.glich.co/dsa/cousins-in-binary-tree/image2.png) 

**Input:** root = [1,2,3,null,4], x = 2, y = 3
**Output:** false

**Constraints:**

* The number of nodes in the tree is in the range `[2, 100]`.
* `1 <= Node.val <= 100`
* Each node has a **unique** value.
* `x != y`
* `x` and `y` are exist in the tree.

# Approaches
## Find Depth and Parent Separately
This straightforward approach involves two independent traversals of the tree. First, we traverse the tree to find the depth and parent of node `x`. Then, we perform a second, separate traversal to find the depth and parent of node `y`. Once we have this information for both nodes, we can easily check if they satisfy the conditions for being cousins (same depth, different parents).
**Time:** O(N). In the worst case, we traverse the entire tree twice, once for `x` and once for `y`. The complexity is O(N) + O(N) = O(N). · **Space:** O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a skewed tree, this can be O(N).
**Pros:** Simple to conceptualize and implement.; The logic for finding a node is cleanly separated from the main comparison logic.
**Cons:** Inefficient as it may traverse the tree twice. If `x` and `y` are in different subtrees, each search might traverse a large portion of the tree.
### Explanation
The core idea is to isolate the problem of finding a node's information. We create a helper function that takes the root and a target value and returns the target's depth and its immediate parent. This function can be implemented using a standard Depth-First Search (DFS). The main function then orchestrates the process by calling this helper twice, once for `x` and once for `y`, and then comparing the returned information to make the final decision.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // A simple class to hold the result of a search
    class NodeInfo {
        TreeNode parent;
        int depth;
        NodeInfo(TreeNode p, int d) {
            this.parent = p;
            this.depth = d;
        }
    }

    public boolean isCousins(TreeNode root, int x, int y) {
        NodeInfo infoX = findNode(root, null, 0, x);
        NodeInfo infoY = findNode(root, null, 0, y);

        return infoX.depth == infoY.depth && infoX.parent != infoY.parent;
    }

    private NodeInfo findNode(TreeNode node, TreeNode parent, int depth, int target) {
        if (node == null) {
            return null;
        }
        if (node.val == target) {
            return new NodeInfo(parent, depth);
        }

        NodeInfo leftResult = findNode(node.left, node, depth + 1, target);
        if (leftResult != null) {
            return leftResult;
        }
        
        return findNode(node.right, node, depth + 1, target);
    }
}
```
### Algorithm
- Create a helper class or structure to hold the result of a search, containing the parent node and the depth.
- Define a recursive helper function, `findNode(node, parent, depth, target)`, that performs a DFS to find the `target` value.
- If the current `node` is null, return null.
- If `node.val` matches the `target`, create and return a new result object with the current `parent` and `depth`.
- Recursively call `findNode` on the left child. If it returns a non-null result, propagate that result up.
- Otherwise, recursively call `findNode` on the right child and return its result.
- In the main `isCousins` function, call the helper function once to find the info for `x`.
- Call the helper function a second time to find the info for `y`.
- Compare the results: return `true` if `infoX.depth == infoY.depth` and `infoX.parent != infoY.parent`.

## Single Depth-First Search (DFS)
This approach improves upon the previous one by finding the required information for both nodes, `x` and `y`, in a single pass through the tree. We can perform a single Depth-First Search (DFS) traversal and keep track of the parent and depth of `x` and `y` as we encounter them.
**Time:** O(N), as we traverse each node at most once. · **Space:** O(H), where H is the height of the tree, for the recursion stack. In the worst case of a skewed tree, this is O(N).
**Pros:** More efficient than two separate traversals as it only requires a single pass over the tree.; The logic is still relatively simple to follow.
**Cons:** Uses class-level variables to maintain state across recursive calls, which can sometimes be less clean than passing state through parameters or return values.; For very deep, skewed trees, the recursion depth could lead to a stack overflow error (though unlikely with the given constraints).
### Explanation
Instead of traversing the tree twice, we can gather all the necessary information in one go. We perform a single DFS from the root. During the traversal, we pass down the current node's parent and its depth. When we find either `x` or `y`, we store their parent and depth information in shared variables. After the traversal is complete, we will have the information for both nodes and can perform the final check.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private TreeNode parentX;
    private TreeNode parentY;
    private int depthX = -1;
    private int depthY = -1;

    public boolean isCousins(TreeNode root, int x, int y) {
        dfs(root, null, 0, x, y);
        return depthX == depthY && parentX != parentY;
    }

    private void dfs(TreeNode node, TreeNode parent, int depth, int x, int y) {
        if (node == null) {
            return;
        }

        if (node.val == x) {
            parentX = parent;
            depthX = depth;
        }
        if (node.val == y) {
            parentY = parent;
            depthY = depth;
        }

        // Optimization: if both found, no need to go deeper
        if (depthX != -1 && depthY != -1) {
            return;
        }

        dfs(node.left, node, depth + 1, x, y);
        
        // Optimization: if both found after left traversal, no need to traverse right
        if (depthX != -1 && depthY != -1) {
            return;
        }
        dfs(node.right, node, depth + 1, x, y);
    }
}
```
### Algorithm
- Initialize class-level variables to store the parent and depth for `x` and `y` (e.g., `parentX`, `depthX`, `parentY`, `depthY`).
- Create a recursive DFS helper function, `dfs(node, parent, depth)`.
- The function traverses the tree. When it encounters `x` or `y`, it records their respective parent and depth in the class-level variables.
- If `node.val == x`, update `parentX` and `depthX`.
- If `node.val == y`, update `parentY` and `depthY`.
- Add an optimization to stop the traversal once both `x` and `y` have been found.
- Recursively call `dfs` for the left and right children, passing `node` as the new parent and `depth + 1` as the new depth.
- After the initial call to `dfs` returns, compare the recorded values: return `true` if `depthX == depthY` and `parentX != parentY`.

## Breadth-First Search (BFS)
Since the definition of cousins is based on depth, a Breadth-First Search (BFS) is a very natural and efficient approach. BFS explores the tree level by level. We can iterate through the tree one level at a time and check if both `x` and `y` appear on the same level, while also ensuring they don't share the same parent.
**Time:** O(N), as each node is visited exactly once. · **Space:** O(W), where W is the maximum width of the tree. This space is used by the queue. In the worst case of a complete binary tree, W can be up to N/2, making the space complexity O(N).
**Pros:** Very efficient as it can terminate early as soon as the conditions are met or violated.; Conceptually clean and a natural fit for problems involving levels/depth.; Iterative approach avoids potential stack overflow issues on very deep trees.
**Cons:** The space complexity can be O(N) for wide, complete binary trees, which might be worse than DFS's O(H) for very deep, narrow trees.
### Explanation
This iterative approach uses a queue to explore the tree layer by layer. The key insight is to process all nodes at a given depth before moving to the next depth. For each level, we check for the presence of `x` and `y`. A crucial part of this approach is checking for the sibling condition: before we even check if a node's value is `x` or `y`, we check if its *children* are `x` and `y`. If they are, we know they share a parent and can immediately conclude they are not cousins.

If we finish a level and find that both `x` and `y` were present, we know they have the same depth and are not siblings, so they must be cousins. If only one was found, they are at different depths, so they cannot be cousins. If neither was found, we continue to the next level.

```java
import java.util.LinkedList;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        if (root == null) {
            return false;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            boolean foundX = false;
            boolean foundY = false;

            // Process one level at a time
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();

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

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

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

            if (foundX && foundY) return true; // Found on same level, not siblings
            if (foundX || foundY) return false; // Found on different levels
        }
        return false;
    }
}
```
### Algorithm
- Initialize a queue for level-order traversal and add the `root`.
- Loop while the queue is not empty.
  - In each iteration, first get the number of nodes at the current level (`levelSize`).
  - Initialize boolean flags `foundX = false` and `foundY = false` for the current level.
  - Loop `levelSize` times to process all nodes on the current level.
    - Dequeue a `node`.
    - **Sibling Check:** Check if the current `node` is the parent of both `x` and `y`. If `node.left` and `node.right` contain `x` and `y`, they are siblings, so return `false` immediately.
    - Check if the `node`'s value is `x` or `y` and update the corresponding boolean flag.
    - Enqueue the non-null children of the `node` for the next level.
  - After processing the level, check the flags:
    - If `foundX` and `foundY` are both true, they are on the same level and are not siblings (due to the earlier check). Return `true`.
    - If only one of `foundX` or `foundY` is true, they are at different depths. Return `false`.
- If the loop completes without returning, it means the nodes were not found as cousins. Return `false`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int x , y ; private TreeNode p1 , p2 ; private int d1 , d2 ; public boolean isCousins ( TreeNode root , int x , int y ) { this . x = x ; this . y = y ; dfs ( root , null , 0 ); return p1 != p2 && d1 == d2 ; } private void dfs ( TreeNode root , TreeNode p , int d ) { if ( root == null ) { return ; } if ( root . val == x ) { p1 = p ; d1 = d ; } if ( root . val == y ) { p2 = p ; d2 = d ; } dfs ( root . left , root , d + 1 ); dfs ( root . right , root , d + 1 ); } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isCousins ( TreeNode * root , int x , int y ) { TreeNode * p1 , * p2 ; int d1 , d2 ; function < void ( TreeNode * , TreeNode * , int ) > dfs = [ & ]( TreeNode * root , TreeNode * fa , int d ) { if ( ! root ) { return ; } if ( root -> val == x ) { p1 = fa ; d1 = d ; } if ( root -> val == y ) { p2 = fa ; d2 = d ; } dfs ( root -> left , root , d + 1 ); dfs ( root -> right , root , d + 1 ); }; dfs ( root , nullptr , 0 ); return p1 != p2 && d1 == d2 ; } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def isCousins ( self , root : Optional [ TreeNode ], x : int , y : int ) -> bool : def dfs ( root , fa , d ): if root is None : return if root . val == x : t [ 0 ] = ( fa , d ) if root . val == y : t [ 1 ] = ( fa , d ) dfs ( root . left , root , d + 1 ) dfs ( root . right , root , d + 1 ) t = [ None , None ] dfs ( root , None , 0 ) return t [ 0 ][ 0 ] != t [ 1 ][ 0 ] and t [ 0 ][ 1 ] == t [ 1 ][ 1 ]
```