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.
1function TreeNode(val, left, right) {
2 this.val = val;
3 this.left = left || null;
4 this.right = right || null;
5}
6
7var isCousins = function(root, x, y) {
8 const queue = [{ node: root, parent: null }];
9 let xInfo = null, yInfo = null;
10
11 while (queue.length) {
12 const levelSize = queue.length;
13 for (let i = 0; i < levelSize; i++) {
14 const { node, parent } = queue.shift();
15
16 if (node.val === x) xInfo = { node, parent };
17 if (node.val === y) yInfo = { node, parent };
18
19 if (xInfo && yInfo) break;
20
21 if (node.left) queue.push({ node: node.left, parent: node });
22 if (node.right) queue.push({ node: node.right, parent: node });
23 }
24
25 if (xInfo && yInfo) return xInfo.parent !== yInfo.parent;
26 if (xInfo || yInfo) return false;
27 }
28
29 return false;
30};In this JavaScript solution, we perform a level-order traversal with the help of a queue. Each node's parent is tracked as we traverse the tree. If both target nodes are found in the same level but have different parents, they are cousins.
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.
1function TreeNode(val, left, right)
This JavaScript solution employs DFS to locate x and y and records their depth and parent details. Using these, we determine if the nodes classify as cousins.