Teaching Kids Programming – Breadth First Search Algorithm to Check if All Leaves in Same Level of Binary Tree

ACMer

4 years ago

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a binary tree root, return whether all leaves are at the same level.

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

Check Same Leaves using Breadth First Search Algorithm

Yesterday, we use the DFS (Depth First Search) Algorithm (Teaching Kids Programming – Depth First Search Algorithm to Check If Leaves are Same Level in Binary Tree) to Push all Levels of Leaves into a set.

With BFS (Breadth First Search) Algorithm, we traverse the binary tree level-by-level, push all levels of leaves into a set, and finally check if the set contains only 1 integer.

# 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 root is None:
            return True
        Q = deque([(root, 0)])
        depths = set()
        while len(Q) > 0:
            cur, d = Q.popleft()
            if cur.left:
                Q.append((cur.left, d + 1))
            if cur.right:
                Q.append((cur.right, d + 1))
            if cur.left is None and cur.right is None:
                depths.add(d)
        return len(depths) == 1

# 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 root is None:
            return True
        Q = deque([(root, 0)])
        depths = set()
        while len(Q) > 0:
            cur, d = Q.popleft()
            if cur.left:
                Q.append((cur.left, d + 1))
            if cur.right:
                Q.append((cur.right, d + 1))
            if cur.left is None and cur.right is None:
                depths.add(d)
        return len(depths) == 1

However, we can just return False without continuing traversing once we know that there are more than 1 levels.

# 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 root is None:
            return True
        Q = deque([(root, 0)])
        depths = set()
        while len(Q) > 0:
            cur, d = Q.popleft()
            if cur.left:
                Q.append((cur.left, d + 1))
            if cur.right:
                Q.append((cur.right, d + 1))
            if cur.left is None and cur.right is None:
                depths.add(d)
                if len(depths) > 1:
                    return False
        return True

# 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 root is None:
            return True
        Q = deque([(root, 0)])
        depths = set()
        while len(Q) > 0:
            cur, d = Q.popleft()
            if cur.left:
                Q.append((cur.left, d + 1))
            if cur.right:
                Q.append((cur.right, d + 1))
            if cur.left is None and cur.right is None:
                depths.add(d)
                if len(depths) > 1:
                    return False
        return True

Alternatively, we can use a variable (last depth integer) to replace the usage of a set:

# 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 root is None:
            return True
        Q = deque([(root, 0)])
        last = -1
        while len(Q) > 0:
            cur, d = Q.popleft()
            if cur.left:
                Q.append((cur.left, d + 1))
            if cur.right:
                Q.append((cur.right, d + 1))
            if cur.left is None and cur.right is None:                
                if last != -1 and d != last:
                    return False
                last = d
        return True

# 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 root is None:
            return True
        Q = deque([(root, 0)])
        last = -1
        while len(Q) > 0:
            cur, d = Q.popleft()
            if cur.left:
                Q.append((cur.left, d + 1))
            if cur.right:
                Q.append((cur.right, d + 1))
            if cur.left is None and cur.right is None:                
                if last != -1 and d != last:
                    return False
                last = d
        return True

–EOF (The Ultimate Computing & Technology Blog) —

559 words
Last Post: Greedy Algorithm to Find Maximum Number After One Swap
Next Post: Algorithm to Sum of Unique Elements

The Permanent URL is: Teaching Kids Programming – Breadth First Search Algorithm to Check if All Leaves in Same Level of Binary Tree (AMP Version)

Check Same Leaves using Breadth First Search Algorithm

Related posts: