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

We can use the Depth First Search algorithm to traverse the binary tree. When we go to the left tree, we decrement the offset, and when we go to the right tree, we increment the offset. We keep all the unique offsets in a hash 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 solve(self, root):
        lines = set()
 
        def dfs(root, x):
            nonlocal lines
            if not root:
                return
            lines.add(x)
            dfs(root.left, x - 1)
            dfs(root.right, x + 1)
 
        dfs(root, 0)
        return len(lines)

# 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):
        lines = set()

        def dfs(root, x):
            nonlocal lines
            if not root:
                return
            lines.add(x)
            dfs(root.left, x - 1)
            dfs(root.right, x + 1)

        dfs(root, 0)
        return len(lines)

Time complexity is O(N) and space complexity is O(N) where N is the number of the nodes in the binary tree. You can also use Breadth First Search algorithm to solve this problem: Teaching Kids Programming – Breadth First Search Algorithm to Count the Vertical Lines in Binary Tree

–EOF (The Ultimate Computing & Technology Blog) —