Teaching Kids Programming – Cousin Nodes in Binary Tree via Breadth First Search & Depth First Search Algorithm


Teaching Kids Programming: Videos on Data Structures and Algorithms

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
2  3

Node 2 and 3 are not cousins because they share the same parent.

    1
   2 3
  4   5

Node 4 and 5 are cousins because they are of same depth/level and they have different parent.

To test if two nodes are cousins, we need to first locate them and this can be done via Depth First Search or Breadth First Search Algorithms.

Depth First Search Algorithm to Check Cousin Nodes in Binary Tree

Recursively visiting the nodes until two nodes have been visited. Remember the nodes’ parent and levels in a hash map (dictionary). Therefore, we need to pass down the level, and the parent information when we recursively visit the left and right subtree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        nodes = {
            x: {
                "level": None,
                "parent": None
            },
            y: {
                "level": None,
                "parent": None
            }
        }
        def dfs(root, parent, level):
            if not root:
                return
            if root.val in nodes:
                nodes[root.val]["level"] = level
                nodes[root.val]["parent"] = parent
            if nodes[x]["level"] != None and nodes[y]["level"] != None:
                return
            dfs(root.left, root, level + 1)    
            dfs(root.right, root, level + 1)    
                        
        dfs(root, None, 0)
 
        return nodes[x]["level"] == nodes[y]["level"] and \
               nodes[x]["parent"] != nodes[y]["parent"]
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        nodes = {
            x: {
                "level": None,
                "parent": None
            },
            y: {
                "level": None,
                "parent": None
            }
        }
        def dfs(root, parent, level):
            if not root:
                return
            if root.val in nodes:
                nodes[root.val]["level"] = level
                nodes[root.val]["parent"] = parent
            if nodes[x]["level"] != None and nodes[y]["level"] != None:
                return
            dfs(root.left, root, level + 1)    
            dfs(root.right, root, level + 1)    
                        
        dfs(root, None, 0)

        return nodes[x]["level"] == nodes[y]["level"] and \
               nodes[x]["parent"] != nodes[y]["parent"]

The time and space complexity for this Recursive Depth First Search Algorithm is O(N) – and we just need to compare the levels and their parents of the given nodes.

Breadth First Search Algorithm to Check Cousin Nodes in Binary Tree

Breadth First Search Algorithm traverses the binary tree (trees, or graphs) in the level-by-level order. We need a Queue (deque namely double-ended queue) to implement a Breadth First Search. We can store the level, parent and the level in the node information.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        nodes = {
            x: {
                "level": None,
                "parent": None
            },
            y: {
                "level": None,
                "parent": None
            }
        }
 
        q = deque([(root, None, 0)])
        while len(q):
            sz = len(q)
            if nodes[x]["level"] != None and nodes[y]["level"] != None:
                break            
            for _ in range(sz): 
                cur, parent, level = q.popleft()
                if cur.val in nodes:
                    nodes[cur.val]["level"] = level
                    nodes[cur.val]["parent"] = parent             
                if cur.left:
                    q.append((cur.left, cur, level + 1))
                if cur.right:
                    q.append((cur.right, cur, level + 1))        
            
        return nodes[x]["level"] == nodes[y]["level"] and \
               nodes[x]["parent"] != nodes[y]["parent"]
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        nodes = {
            x: {
                "level": None,
                "parent": None
            },
            y: {
                "level": None,
                "parent": None
            }
        }

        q = deque([(root, None, 0)])
        while len(q):
            sz = len(q)
            if nodes[x]["level"] != None and nodes[y]["level"] != None:
                break            
            for _ in range(sz): 
                cur, parent, level = q.popleft()
                if cur.val in nodes:
                    nodes[cur.val]["level"] = level
                    nodes[cur.val]["parent"] = parent             
                if cur.left:
                    q.append((cur.left, cur, level + 1))
                if cur.right:
                    q.append((cur.right, cur, level + 1))        
            
        return nodes[x]["level"] == nodes[y]["level"] and \
               nodes[x]["parent"] != nodes[y]["parent"]

However, as we are always popping all nodes in the queue (who are belonging to same levels), we can instead use a level variable:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        nodes = {
            x: {
                "level": None,
                "parent": None
            },
            y: {
                "level": None,
                "parent": None
            }
        }
 
        q = deque([(root, None)])
        level = 0
        while len(q):
            sz = len(q)
            level += 1
            if nodes[x]["level"] != None and nodes[y]["level"] != None:
                break            
            for _ in range(sz): 
                cur, parent = q.popleft()
                if cur.val in nodes:
                    nodes[cur.val]["level"] = level
                    nodes[cur.val]["parent"] = parent             
                if cur.left:
                    q.append((cur.left, cur))
                if cur.right:
                    q.append((cur.right, cur))        
            
        return nodes[x]["level"] == nodes[y]["level"] and \
               nodes[x]["parent"] != nodes[y]["parent"]
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        nodes = {
            x: {
                "level": None,
                "parent": None
            },
            y: {
                "level": None,
                "parent": None
            }
        }

        q = deque([(root, None)])
        level = 0
        while len(q):
            sz = len(q)
            level += 1
            if nodes[x]["level"] != None and nodes[y]["level"] != None:
                break            
            for _ in range(sz): 
                cur, parent = q.popleft()
                if cur.val in nodes:
                    nodes[cur.val]["level"] = level
                    nodes[cur.val]["parent"] = parent             
                if cur.left:
                    q.append((cur.left, cur))
                if cur.right:
                    q.append((cur.right, cur))        
            
        return nodes[x]["level"] == nodes[y]["level"] and \
               nodes[x]["parent"] != nodes[y]["parent"]

BFS algorithms usually take O(N) time and space – so is this one.

See also the C++ algorithm to test cousin nodes in binary tree: The Cousins in Binary Tree

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
906 words
Last Post: Teaching Kids Programming - Restore the Word from Rules
Next Post: Teaching Kids Programming - Kth Smallest Element in a BST via Iterative Inorder Traversal Algorithm

The Permanent URL is: Teaching Kids Programming – Cousin Nodes in Binary Tree via Breadth First Search & Depth First Search Algorithm

Leave a Reply