Leetcode 0993. Cousins in Binary Tree

Problem statement

https://leetcode.com/problems/cousins-in-binary-tree/

Solution

The idea is to use dfs(node, par, dep, val). For each of two given valuex x, y we need to find depth and parent. Nodes are cousins if they have the same depth and different parents.

Complexity

It is O(n) for time and O(h) for space.

Code

class Solution:
    def isCousins(self, root, x, y):
        def dfs(node, par, dep, val):
            if not node: return
            if node.val == val: return dep, par
            return dfs(node.left, node, dep + 1, val) or dfs(node.right, node, dep + 1, val)
        
        dep_x, par_x = dfs(root, None, 0, x)
        dep_y, par_y = dfs(root, None, 0, y)

        return dep_x == dep_y and par_x != par_y