> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/tree/993.-cousins-in-binary-tree.md).

# 993. Cousins in Binary Tree

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

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

We are given the `root` of a binary tree with unique values, and the values `x` and `y` of two different nodes in the tree.

Return `true` if and only if the nodes corresponding to the values `x` and `y` are cousins.

**Example 1:**\
![](https://assets.leetcode.com/uploads/2019/02/12/q1248-01.png)

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

**Example 2:**\
![](https://assets.leetcode.com/uploads/2019/02/12/q1248-02.png)

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

**Example 3:**

![](https://assets.leetcode.com/uploads/2019/02/13/q1248-03.png)

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

**Note:**

1. The number of nodes in the tree will be between `2` and `100`.
2. Each node has a unique integer value from `1` to `100`.

```cpp
// Recursion (Preorder Traversal)
void helper(TreeNode* node, int x, int y, int depth, TreeNode* parent, TreeNode*& x_parent, TreeNode*& y_parent, int& x_depth, int& y_depth) {
    if (!node) return;
    if (node->val == x) {
        x_parent = parent;
        x_depth = depth;
    } else if (node->val == y) {
        y_parent = parent;
        y_depth = depth;
    } else { // once x or y is found, there is no need to go deeper
        helper(node->left, x, y, depth + 1, node, x_parent, y_parent, x_depth, y_depth);
        helper(node->right, x, y, depth + 1, node, x_parent, y_parent, x_depth, y_depth);
    }
}
bool isCousins(TreeNode* root, int x, int y) { // time: O(n); space: O(n)
    TreeNode *x_parent = nullptr, *y_parent = nullptr;
    int x_depth = -1, y_depth = -1;
    helper(root, x, y, 0, nullptr, x_parent, y_parent, x_depth, y_depth);
    return (x_depth == y_depth && x_parent != y_parent);
}
```

```cpp
// BFS Lever Order Traversal
bool isCousins(TreeNode* root, int x, int y) { // time: O(n); space: O(n)
    queue<TreeNode*> q({root});
    while (!q.empty()) {
        int sz = q.size();
        bool x_exist = false, y_exist = false;
        // A level in BFS
        for (int i = 0; i < sz; ++i) {
            TreeNode* cur = q.front(); q.pop();
            if (cur->val == x) x_exist = true;
            else if (cur->val == y) y_exist = true;
            if (cur->left && cur->right) {
                if ((cur->left->val == x && cur->right->val == y) ||
                    (cur->left->val == y && cur->right->val == x)) return false; 
            }
            if (cur->left) {
                q.push(cur->left);
            }
            if (cur->right) {
                q.push(cur->right);
            }
        }
        if (x_exist && y_exist) return true;
        else if (x_exist || y_exist) return false; // x and y are not in the same depth level
    }
    return false;
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/tree/993.-cousins-in-binary-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.