Cousins in Binary Tree

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.

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

The problem Cousins in Binary Tree can be solved by finding a path to x and y using a depth-first search and checking if the paths have same lengths and if the paths are not identical.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

/**
 * 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 helper(TreeNode *root, int val, vector<int> &path)
    {
        if (root == NULL)
            return false;

        if (root->val == val || helper(root->left, val, path) || helper(root->right, val, path))
        {
            path.push_back(root->val);
            return true;
        }

        return false;
    }

    bool isCousins(TreeNode *root, int x, int y)
    {
        vector<int> x_path, y_path;
        helper(root, x, x_path);
        helper(root, y, y_path);

        if (x_path.size() == y_path.size())
            for (int i = 1; i < x_path.size(); i++)
                if (x_path[i] != y_path[i])
                    return true;

        return false;
    }
};