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.
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:
[2, 100].1 <= Node.val <= 100x != yx and y are exist in the tree.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.
In this Python solution, we use a deque to facilitate a level-order traversal. We track both the parent and depth of each node and check if the target nodes are at the same depth but have different parents. If they do, they are cousins.
JavaScript
C++
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.
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).
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.
JavaScript
C++
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.
| Approach | Complexity |
|---|---|
| Level Order Traversal | Time Complexity: O(n), where n is the number of nodes in the tree, as it requires visiting each node once. |
| Depth First Search with Parent and Depth Tracking | Time Complexity: O(n) where n is the total nodes count due to entire tree traversal. |
Cousins in a binary tree | Leetcode #993 • Techdose • 37,620 views views
Watch 9 more video solutions →Practice Cousins in Binary Tree with our built-in code editor and test cases.
Practice on FleetCode