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:

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

Example 2:

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

Example 3:

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.

// 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);
}

// 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;
}