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

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

October 18, 2021 No Comments algorithms, BFS, DFS, teaching kids programming, youtube video

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

Related posts:

  1. Fixing Profile Query Command due to API Change in Steem Blockchain Due to an API change in SteemIt see this post, the following code to get...
  2. Teaching Kids Programming – Closest Binary Search Tree Value (Recursion + Inorder Traversal + Binary Search Algorithm) Teaching Kids Programming: Videos on Data Structures and Algorithms Given the root of a binary...
  3. Teaching Kids Programming – Algorithms to Find the Lowest Common Ancestor of a Binary Search Tree Teaching Kids Programming: Videos on Data Structures and Algorithms Given a binary search tree (BST),...
  4. Teaching Kids Programming – Recursive Algorithm to Prune a Binary Tree Teaching Kids Programming: Videos on Data Structures and Algorithms Given the root of a binary...
  5. The Young Prompt Engineers My sons were excited to show me the Text to Image feature using Microsoft Bing....
  6. The Review of cozmo robot from Anki The ANKI COZMO robot is fun – I got it from Amazon and it is...
  7. How to Determine Sum of Two Square Numbers? Given a non-negative integer c, your task is to decide whether there’re two integers a...
  8. The Secure Shell (SSH) Chrome Extension developed by Google Speaking about SSH tools, we often use the PuTTY or Termius, which are heavy weight...

Leave a Reply