Sponsored
Sponsored
This approach utilizes Level Order Traversal (Breadth-First) to determine if two nodes are cousins. During traversal, track the parent and depth of each node until both target nodes are found, then verify if they qualify as cousins.
Time Complexity: O(n), where n is the number of nodes in the tree, as it requires visiting each node once.
Space Complexity: O(n) for storing the nodes in the queue.
1#include <queue>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode() : val(0), left(nullptr), right(nullptr) {}
9 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15 bool isCousins(TreeNode* root, int x, int y) {
16 queue<pair<TreeNode*, TreeNode*>> q; // node, parent
17 q.push({root, nullptr});
18 pair<TreeNode*, TreeNode*> xInfo = {nullptr, nullptr}, yInfo = {nullptr, nullptr};
19
20 while (!q.empty()) {
21 int levelSize = q.size();
22 for (int i = 0; i < levelSize; i++) {
23 auto [node, parent] = q.front();
24 q.pop();
25
26 if (node->val == x) xInfo = {node, parent};
27 if (node->val == y) yInfo = {node, parent};
28
29 if (xInfo.first && yInfo.first) break;
30
31 if (node->left) q.push({node->left, node});
32 if (node->right) q.push({node->right, node});
33 }
34
35 if (xInfo.first && yInfo.first)
36 return xInfo.second != yInfo.second;
37 if (xInfo.first || yInfo.first)
38 return false;
39 }
40
41 return false;
42 }
43};In this C++ solution, a queue is used for level-order traversal where we store each node and their parent. The process checks whether the target nodes have different parents and return appropriate results accordingly.
This approach uses a DFS to recursively track the parent and depth of each node. On finding nodes x and y, checks are done whether they meet cousin criteria (same depth and different parents).
Time Complexity: O(n) where n is the total nodes count due to entire tree traversal.
Space Complexity: O(h) with h as the height of the tree, due to recursive stack space usage.
1class TreeNode:
2 def
This Python implementation uses DFS to recursively find the depth and parents of x and y. When both found, checks are done to validate if they are cousins by comparing depth and parent values.