[Solved] 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.

Table of Contents

Question

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 the depth 0, and children of each depth k node are at the depth k + 1.

Example 1:

q1248 01
Input: root = [1,2,3,4], x = 4, y = 3
Output: false

Example 2:

q1248 02
Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true

Example 3:

q1248 03
Input: root = [1,2,3,null,4], x = 2, y = 3
Output: false

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.

Python Solution

def traverse(root,parent,level,x,y):
    global p1,p2,l1,l2
    if root==None:return
    
    if root.val==x:
        p1 = parent.val if parent else None
        l1 = level
    if root.val==y:
        p2 = parent.val if parent else None
        l2 = level
    
    traverse(root.left,root,level+1,x,y)
    traverse(root.right,root,level+1,x,y)
    
    
class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        global p1,p2,l1,l2
        p1=None
        p2=None
        l1=0
        l2=0
        traverse(root,None,1,x,y)
        return p1!=p2 and l1==l2

Leave a Reply

Your email address will not be published. Required fields are marked *