?? Exploring Binary Tree Relationships: Unraveling Cousins

?? Problem: 993 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.

Binary tree relationships

        1
       / \
      /   \
     2     3
    / \     \
   4   6*    5

Current Node: 6
- Parent: 2
- Depth: 2
- Siblings: [4]
- Cousins: [5]        

?? Approach - Recursive DFS Preorder

The algorithm checks if two nodes with values x and y in a binary tree are cousins, meaning they share the same depth but have different parents. It recursively traverses the tree to find the depths and parents of the given nodes x and y, then compares their depths and parents to determine if they are cousins.

?? Complexity Analysis:

Time complexity: O(n), where n is the number of nodes in the binary tree

Space complexity: O(h), where h is the height of the binary tree

?? Code Representation:

class Solution:
  def isCousins(self, root, x, y) -> bool:

    self.x_node = (None, -1)
    self.y_node = (None, -1)
                
    def helper(node, parent, depth):
      if not node:
        return 0
            
      if node.val == x:
        self.x_node = (parent, depth)

      if node.val == y:
        self.y_node = (parent, depth)

      helper(node.left, node, depth+1)
      helper(node.right, node, depth+1)

    helper(root, None, 0)

    if self.x_node[0] != self.y_node[0] and
    self.x_node[1] == self.y_node[1]:

      return True
    return False        

?? Solution Links:

Recursive DFS preorder

Iterative DFS preorder

?? Key Takeaways:

Cousins in binary trees are nodes that share the same depth but have different parents, offering an interesting challenge in tree traversal and node comparison.

The recursive approach efficiently explores the tree's structure to identify cousins, leveraging depth-first search (DFS) principles.

?? Join the Discussion:

Engage with fellow enthusiasts as we explore the intricacies of binary tree traversal and problem-solving strategies. Have you faced challenges in uncovering the mysteries of binary trees? Let's exchange insights, experiences, and best practices to deepen our understanding of algorithms and data structures! Connect with me on LinkedIn to continue the discussion.

#programming #softwareengineering #python #algorithms #datastructures #leetcode

LeetCode