Teaching Kids Programming – Breadth First Search Algorithm to Find the Only Child in Binary Tree


Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a binary tree root, return the number of nodes that are an only child. A node x is an only child if its parent has exactly one child (x).

Constraints
n ≤ 100,000 where n is the number of nodes in root

only-child-binary-tree Teaching Kids Programming - Breadth First Search Algorithm to Find the Only Child in Binary Tree algorithms BFS python teaching kids programming youtube video

Using BFS Algorithm to Find the Only Child in Binary Tree

We can use the BFS (Breadth First Search) Algorithm, to traverse the binary tree. While we expanding the node into the queue, we know record the number of the children for the current node. Thus, we accumulate the only child when the count is 1.

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
# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def solve(self, root):
        if not root:
            return 0
        q = deque([(root, -1)])
        ans = 0
        while q:
            cur, cnt = q.popleft()
            if cnt == 1:
                ans += 1
            x = 0
            if cur.left:
                x += 1
            if cur.right:
                x += 1
            if cur.left:                
                q.append((cur.left, x))
            if cur.right:
                q.append((cur.right, x))
        return ans                
# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def solve(self, root):
        if not root:
            return 0
        q = deque([(root, -1)])
        ans = 0
        while q:
            cur, cnt = q.popleft()
            if cnt == 1:
                ans += 1
            x = 0
            if cur.left:
                x += 1
            if cur.right:
                x += 1
            if cur.left:                
                q.append((cur.left, x))
            if cur.right:
                q.append((cur.right, x))
        return ans                

The time complexty is O(N) where N is the number of the nodes in the binary tree and the space complexity is O(N) as we are using a queue to implement the BFS.

See also: Counting the Only Child in the Binary Tree using Breadth First Search Algorithm

Finding only child in binary tree can be also solved using Depth First Search Algorithm: Teaching Kids Programming – Depth First Search Algorithm to Find the Only Child in Binary Tree

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
a WordPress rating system
455 words
Last Post: Counting the Number of Different Integers in a String
Next Post: Finding the Second Largest Digit in a String

The Permanent URL is: Teaching Kids Programming – Breadth First Search Algorithm to Find the Only Child in Binary Tree

Leave a Reply