{x}
blog image

Cousins in Binary Tree

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:

  • The number of nodes in the tree is in the range [2, 100].
  • 1 <= Node.val <= 100
  • Each node has a unique value.
  • x != y
  • x and y are exist in the tree.

Solution Explanation:

This problem asks to determine if two nodes in a binary tree are cousins. Two nodes are cousins if they are at the same depth but have different parents. The solutions presented utilize Breadth-First Search (BFS) and Depth-First Search (DFS) approaches.

Approach 1: Breadth-First Search (BFS)

This approach uses a queue to perform a level-order traversal of the binary tree. For each node, we keep track of its parent and depth.

  1. Initialization: A queue q is initialized with the root node and its parent (initially None or null). Variables p1, p2, d1, d2 store the parent and depth of nodes x and y respectively.

  2. Level-Order Traversal: The while loop iterates through levels of the tree. The inner loop processes all nodes at the current level.

  3. Node Check: For each node, we check if its value is equal to x or y. If found, we update the corresponding parent (p1 or p2) and depth (d1 or d2).

  4. Children Enqueue: If a node has children, they are added to the queue along with their parent (the current node).

  5. Cousins Check: After the traversal, we check if p1 is not equal to p2 (different parents) and d1 is equal to d2 (same depth). If both conditions are true, the nodes are cousins, and true is returned; otherwise, false is returned.

Approach 2: Depth-First Search (DFS)

This approach uses recursion to perform a depth-first traversal. It directly tracks parent and depth during traversal.

  1. Recursive Function dfs: The recursive function dfs takes the current node, its parent, and its depth as input.

  2. Node Check: If the current node's value is x or y, its parent and depth are stored in st[0] or st[1] respectively.

  3. Recursive Calls: Recursive calls are made for the left and right children.

  4. Cousins Check: After the DFS traversal, the function checks if st[0] and st[1] contain different parents but the same depth.

Time and Space Complexity Analysis:

Approach 1 (BFS):

  • Time Complexity: O(N), where N is the number of nodes in the tree. BFS visits each node once.
  • Space Complexity: O(W), where W is the maximum width of the tree. In the worst case (a complete binary tree), W can be O(N). The queue stores nodes at each level.

Approach 2 (DFS):

  • Time Complexity: O(N). DFS visits each node once.
  • Space Complexity: O(H), where H is the height of the tree. In the worst case (a skewed tree), H can be O(N). The space is used for the recursive call stack.

In summary, both approaches have a time complexity of O(N) and a space complexity that depends on the tree's structure. BFS has a space complexity related to the tree's width, while DFS has a space complexity related to the tree's height. For balanced trees, both approaches are efficient; for skewed trees, DFS might use less space. The choice depends on the specific tree structure and space efficiency requirements.