LeetCode: 993. Cousins in Binary Tree

The 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

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

Example 2

Input:  [1,2,3,null,4], x = 2, y = 3
Output: false, the reason is simple both are at the same level but the parent is the same.

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.

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

struct Answer {
    int x, y;
    int parentX, parentY;

    bool areCousins() {
	    return x == y && parentX != parentY;
    }
};

bool isCousins(TreeNode* root, int x, int y) {
    Answer answer;
    isCousins(root, answer, x, y, 1, root->val);
    return answer.areCousins();
}

void isCousins( TreeNode* root, Answer &answer, int x, int y, int floor, int parent) {

    if(root == nullptr) return;

    if(root->val == x) {
        answer.x = floor;
        answer.parentX = parent;
    }

    if(root->val == y) {
        answer.y = floor;
        answer.parentY = parent;
    } 

    isCousins(root->left, answer, x, y, floor + 1, root->val );
    isCousins(root->right, answer, x, y, floor + 1, root->val );
}

Let's break down the code step by step:

1. The code defines a struct Answer with four integer fields: x, y, parentX, and parentY. These fields are used to store information about the levels and parents of two nodes, which we want to check for being cousins.

2. Inside the Answer struct, there's a member function areCousins(): this function checks if the stored levels x and y are the same (meaning the nodes are at the same level) and also checks if their parent values parentX and parentY are different (meaning the nodes have different parents). If both conditions are met, it returns true, indicating that the nodes are cousins.

3. The isCousins function is defined: This is the main function that the user can call. It takes a pointer to the root node of a binary tree and two integer values x and y representing the nodes we want to check for being cousins.

Inside this function:

• An instance of the Answer struct named answer is created.
• The function isCousins(root, answer, x, y, 1, root->val) is called, passing in the root node, the answer instance, the two node values x and y, the current level 1, and the value of the root node itself.

4. The recursive helper function isCousins is defined:

This function recursively traverses the binary tree to find the levels and parents of the nodes x and y.

• If the current node's value is equal to x, it updates the answer with the floor (level) and parentX (parent's value).
• If the current node's value is equal to y, it updates the answer with the floor (level) and parentY (parent's value).
• Then, it recursively calls itself on the left and right subtrees, increasing the level (floor + 1) and passing the current node's value as the parent value.