algoadvance

Leetcode 993. Cousins in Binary Tree

Problem Statement:

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.

Given the root of a binary tree with unique values, and the values of two different nodes x and y, 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

Constraints:

• The number of nodes in the tree is in the range [2, 100].
• Each node has a unique integer value.

Clarifying Questions:

1. What should be returned if x or y is not present in the tree?
   • We can assume both x and y are guaranteed to be in the tree according to the problem statement.
2. Can the tree contain duplicate values?
   • No, as per the problem statement, each node has a unique integer value.
3. What are the edge cases to consider?
   • Nodes x and y might be at different depths or might have the same parent.

Strategy:

1. Breadth-First Search (BFS):
   • Use a queue to perform a level-order traversal (BFS).
   • For each node visited, keep track of its depth and parent node.
   • When we find node x, record its depth and parent.
   • When we find node y, record its depth and parent.
   • After traversal, check if x and y have the same depth but different parents.

Code:

#include <iostream>
#include <queue>
#include <tuple>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        if (!root) return false;
        
        queue<tuple<TreeNode*, int, TreeNode*>> q;
        q.push({root, 0, nullptr});  // Tuple of (node, depth, parent)
        
        int x_depth = -1, y_depth = -1;
        TreeNode* x_parent = nullptr;
        TreeNode* y_parent = nullptr;
        
        while (!q.empty()) {
            auto[node, depth, parent] = q.front(); q.pop();
            
            if (node->val == x) {
                x_depth = depth;
                x_parent = parent;
            } else if (node->val == y) {
                y_depth = depth;
                y_parent = parent;
            }
            
            if (x_depth != -1 && y_depth != -1) {
                break;  // Stop searching if both nodes are found
            }
            
            if (node->left) {
                q.push({node->left, depth + 1, node});
            }
            if (node->right) {
                q.push({node->right, depth + 1, node});
            }
        }
        
        return x_depth == y_depth && x_parent != y_parent;
    }
};

Time Complexity:

• Time Complexity: O(n), where n is the number of nodes in the binary tree. The BFS traversal ensures that each node is visited exactly once.
• Space Complexity: O(n), due to the queue used for the BFS, which in the worst case, stores one level of the tree nodes.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?