README.md

993. Cousins in Binary Tree

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.

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.

Solutions (Python)

1. DFS

# 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:
        parent, depth = {root.val: None}, {}
        def dfs(root: TreeNode, dep: int):
            depth[root.val] = dep
            if root.left:
                parent[root.left.val] = root
                dfs(root.left, dep + 1)
            if root.right:
                parent[root.right.val] = root
                dfs(root.right, dep + 1)

        dfs(root, 0)
        return depth[x] == depth[y] and parent[x] != parent[y]

2. BFS

# 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:
        nodes = [root]
        while nodes:
            nodes = [node.left for node in nodes if node] \
                + [node.right for node in nodes if node]
            vals = [node.val if node else 0 for node in nodes]
            if x in vals and y in vals:
                return abs(vals.index(x) - vals.index(y)) != len(vals) / 2
            elif x in vals or y in vals:
                return False