Teaching Kids Programming – Depth 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

Using DFS Algorithm to Find the Only Child in Binary Tree

We can use the Breadth First Search Algorithm to find the only child nicely: Teaching Kids Programming – Breadth First Search Algorithm to Find the Only Child in Binary Tree. BFS traverses the binary tree level by level and we record the number of children for the current node’s parent when we expand children nodes in the next level.

We can do this using Depth First Search Algorithm as well where we traverse the binary tree using Recursion. And we need to pass down the number of children for the current node’s parent. This way, we can accumulate the answer for the number of the only child nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countingOnlyChild(self, root):
        def dfs(root, cnt):
            if root is None:
                return 0
            ans = 0
            if cnt == 1:
                ans += 1
            x = 0
            if root.left:
                x += 1
            if root.right:
                x += 1
            ans += dfs(root.left, x)
            ans += dfs(root.right, x)
            return ans
        return dfs(root, 0)                        

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countingOnlyChild(self, root):
        def dfs(root, cnt):
            if root is None:
                return 0
            ans = 0
            if cnt == 1:
                ans += 1
            x = 0
            if root.left:
                x += 1
            if root.right:
                x += 1
            ans += dfs(root.left, x)
            ans += dfs(root.right, x)
            return ans
        return dfs(root, 0)                        

The time complexity is also O(N) as compared to BFS. N is the number of the nodes in the given binary tree. The space complexity is O(N) as we are using Recursion which has implicit usage of Stack.

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

–EOF (The Ultimate Computing & Technology Blog) —