> For the complete documentation index, see [llms.txt](https://yyloumike.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yyloumike.gitbook.io/leetcode/tree/binary-tree-traversal-3-qs/0993.-cousins-in-binary-tree.md).

# 0993. Cousins in Binary Tree

Easy  |  Tree + Level-order Traversal  |  24 ms (97.60%),  14.1 MB (97.24%)

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Cousins in Binary Tree](https://leetcode.com/problems/cousins-in-binary-tree/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0993-cousins-in-binary-tree)

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 depth 0**, and children of each depth `k` node are at the depth `k + 1`.
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**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.
  {% endtab %}
  {% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
Extension question of **Level-order traversal**.
{% endhint %}

While traversing the tree in level order, we need **additional information**:

* Whenever we append a node onto the stack, we need to record its **parent node**.
* We need to know **which level (depth) we are at** since *cousin nodes exist in the same depth*. That is to say, **if we only find one node instead of two nodes, there is no cousin node existing**.
  {% endtab %}
  {% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        
        # ==================================================
        #  Binary Tree + Level Order Traversal             =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        depth = 0
        target = None
        stack = [(root, None)]
        
        while stack:
            for i in range(len(stack)):
                node, parent = stack.pop(0)
                
                if node.val == x or node.val == y:
                    if target:
                        return True if depth == target[0] and parent != target[1] else False
                    target = (depth, parent)
            
                if node.left: stack.append((node.left, node))
                if node.right: stack.append((node.right, node))
            
            if target: return False
            depth += 1
            
        return False
```

{% endtab %}
{% endtabs %}