0993. Cousins in Binary Tree

Easy | Tree + Level-order Traversal | 24 ms (97.60%), 14.1 MB (97.24%)

❓ Problem Statement

Source: LeetCode - Cousins in Binary Tree GitHub: Solution / Performance

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.

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

✍🏻 Constraints & Example

Constraints:

• The number of nodes in the tree is in the range [2, 100].

• 1 <= Node.val <= 100

• Each node has a unique value.

• x != y

• x and y are exist in the tree.

💡 Ideas

Extension question of Level-order traversal.

While traversing the tree in level order, we need additional information:

• Whenever we append a node onto the stack, we need to record its parent node.

• We need to know which level (depth) we are at since cousin nodes exist in the same depth. That is to say, if we only find one node instead of two nodes, there is no cousin node existing.

🤖 Python3

class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        
        # ==================================================
        #  Binary Tree + Level Order Traversal             =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        depth = 0
        target = None
        stack = [(root, None)]
        
        while stack:
            for i in range(len(stack)):
                node, parent = stack.pop(0)
                
                if node.val == x or node.val == y:
                    if target:
                        return True if depth == target[0] and parent != target[1] else False
                    target = (depth, parent)
            
                if node.left: stack.append((node.left, node))
                if node.right: stack.append((node.right, node))
            
            if target: return False
            depth += 1
            
        return False