993. Cousins in Binary Tree (Python)

Related Topic

Breadth-First-Search.

Description

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.

Two nodes of a binary tree are cousins if they have the same depth, but have different parents.

We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.

Return true if and only if the nodes corresponding to the values x and y are cousins.

Sample I/O

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

Note

1. The number of nodes in the tree will be between 2 and 100.
2. Each node has a unique integer value from 1 to 100.

Methodology

Use BFS traversal the tree level by level for each node, if the node have children. then append the node value (as parent), child value and depth to a dictionary. After traversal the tree. We need to find x, y node’s parent and depth from dictionary. If they have same depth but different parent return true otherwise return false.

Code (BFS)

def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        queue = collections.deque()
        queue.append((root,0))
        dist={}
        while queue:
            node,depth = queue.popleft()
            if node.left:
                dist[node.left.val]=(node.val,depth+1)
                queue.append((node.left,depth+1))
            if node.right:
                dist[node.right.val]=(node.val,depth+1)
                queue.append((node.right,depth+1))
        if x not in dist or y not in dist: return False
        x_parent,x_depth = dist[x]
        y_parent,y_depth = dist[y]
        return x_depth == y_depth and x_parent != y_parent

BigO

We traversal all elements of tree once so total time complexity is O(n) where n is number of the tree nodes.