Python program to print cousins of a given node in Binary Tree

In this tutorial, we shall be printing the cousins of a given node in Binary Tree in Python. The cousins of the given node are the nodes that are at the same level as the given node but do not have the same parent node as the given node. A sibling node is a node that shares the parent node as the given node. Since we only need the cousins, the sibling of the given Node should not be printed.

Input : root of below tree 
             1
           /   \
          2     3
        /   \  /  \
       4    5  6   7
       and pointer to a node say 6

Output : 4 5

Input : root of below tree 
             1
           /   \
          2     3
        /   \  /  \
       4    5  6   7
      / \  / \  \   \
     8  9 10  11 12  13
     and pointer to a node say 9

Output : 10 11 12 13

Print cousins of a given node in Binary Tree in Python

Firstly, we find the level at which the given node is present. In this scenario, Root is considered as level 1. We increase the level and traverse the left subtree. If the given node is found, we return the level and if not found, we traverse the right subtree. nodeLevel function in our program is used to calculate the level of the given node.

Secondly, we find the nodes which are at the same level as the given node. The algorithm works as if the given node is at level 1 and root at the calculated level L. As a result, the cousins will be the children of level 2 nodes from the given node.

Program

class newNode: 
  def __init__(self, item): 
    self.data = item 
    self.left = self.right = None

def nodeLevel(root, node, level): 
  if (root == None): 
    return 0
  if (root == node): 
    return level 
  nextlevel = nodeLevel(root.left, node, level + 1) 
  if (nextlevel != 0): # =0 if node not present in left subtree of root
    return nextlevel 
  return nodeLevel(root.right, node, level + 1) 
 
def printCousins(root, node, level): 

  if (root == None or level < 2): 
    return

  if (level == 2): 
    if (root.left == node or root.right == node): #sibling case
      return
    if (root.left): 
      print(root.left.data, end = " ") 
    if (root.right): 
      print(root.right.data, end = " ") 

  # Recur for left and right subtrees 
  elif (level > 2): 
    printCousins(root.left, node, level - 1) 
    printCousins(root.right, node, level - 1) 

def cousins(root, node):
  level = nodeLevel(root, node, 1)
  printCousins(root, node, level)

# Driver Code 
if __name__ == '__main__': 
  root = newNode(1)  
  root.left = newNode(2)  
  root.right = newNode(3)  
  root.left.left = newNode(4)  
  root.left.right = newNode(5)  
  root.right.left = newNode(6)  
  root.right.right = newNode(7)  
  root.left.left.left = newNode(8)
  root.left.left.right = newNode(9)
  root.left.right.left = newNode(10)
  root.left.right.right = newNode(11)
  root.right.left.right = newNode(12)
  root.right.right.right = newNode(13)

  cousins(root, root.left.left.right)

Output: 10 11 12 13

Also Read: Binary heap implementation in Python