Cousins in Binary Tree

Problem Id: 993 Difficulty: Easy Tag: Tree Tag: Breadth-first Search


Intuition

This problem could be solved by 2 steps.

  1. Use DFS to get the depths of node1 and node2 and their parents.
  2. Compare their depths and parents to get the result.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        self.p1 = None
        self.q1 = None
        self.d1 = -1
        self.d2 = -1
        self._helper(root, None, 0, x, y)
        return (self.d1 == self.d2) and (self.p1 != self.p2)

    def _helper(self, node, parent, depth, x, y):
        if node is None:
            return
        if node.val == x:
            self.d1 = depth
            self.p1 = parent
        elif node.val == y:
            self.d2 = depth
            self.p2 = parent
        self._helper(node.left, node, depth + 1, x, y)
        self._helper(node.right, node, depth + 1, x, y)