993. Cousins in Binary Tree

2023, Mar 12 2 mins read

1. Description

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.

2. Example

Example 1

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

Example 2

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

Example 3

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

3. 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.

4. Solutions

Depth-First Search

n is the number of nodes in root
Time complexity: O(n)
Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    bool isCousins(TreeNode *root, int x, int y) {
        traverse(root, x, y, 0);

        return (x_parent != y_parent) && (x_depth_ == y_depth_);
    }

    void traverse(TreeNode *root, int x, int y, int depth) {
        if (root != nullptr) {
            if (root->left != nullptr && root->left->val == x ||
                root->right != nullptr && root->right->val == x) {
                x_depth_ = depth + 1;
                x_parent = root;
            } else if (
                root->left != nullptr && root->left->val == y ||
                root->right != nullptr && root->right->val == y) {
                y_depth_ = depth + 1;
                y_parent = root;
            }

            traverse(root->left, x, y, depth + 1);
            traverse(root->right, x, y, depth + 1);
        }
    }

private:
    int x_depth_ = 0;
    TreeNode *x_parent = nullptr;
    int y_depth_ = 0;
    TreeNode *y_parent = nullptr;
};