Teaching Kids Programming – Breadth First Search Algorithm to Count the Vertical Lines in Binary Tree

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a binary tree root, return the number of unique vertical lines that can be drawn such that every node has a line intersecting it. Each left child is angled at 45 degrees to its left, while the right child is angled at 45 degrees to the right.

For example, root and root.left.right are on the same vertical line.

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

Vertical Lines in Binary Tree via BFS Algorithm

We can use the Breadth First Search Algorithm to traverse the binary tree level by level order. While going through left child, we decrement the horizontal offset by 1 and while navigating to the right child, we increment the horizontal offset. We keep unique offsets in a hash set and the answer is the length of the set.

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

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def numberOfVerticalLinesBinaryTree(self, root):
        if not root:
            return 0
        q = deque([(root, 0)])
        data = set()
        while q:
            cur, x = q.popleft()
            data.add(x)
            if cur.left:
                q.append((cur.left, x - 1))
            if cur.right:
                q.append((cur.right, x + 1))
        return len(data)

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def numberOfVerticalLinesBinaryTree(self, root):
        if not root:
            return 0
        q = deque([(root, 0)])
        data = set()
        while q:
            cur, x = q.popleft()
            data.add(x)
            if cur.left:
                q.append((cur.left, x - 1))
            if cur.right:
                q.append((cur.right, x + 1))
        return len(data)

The time complexity is O(N) and the space compleixty is O(N) where N is the number of nodes in the binary tree. We can use the Depth First Search Algorithm to Traverse the Binary Tree: Teaching Kids Programming – Depth First Search Algorithm to Count the Vertical Lines in Binary Tree

–EOF (The Ultimate Computing & Technology Blog) —