Teaching Kids Programming – Longest Path in Binary Tree via Diameter Algorithm (DFS + BFS)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a binary tree root, return the longest path between any two nodes in the tree.

Constraints
n ≤ 100,000 where n is the number of nodes in root
Example 1
Input
root = [0, [1, null, null], [2, [3, [4, null, null], null], [0, null, null]]]
Output
5

Explanation
A longest path is [1, 0, 2, 3, 4]

Example 2
Input
root = [0, null, [2, [3, [4, null, null], null], [0, null, [6, null, [7, null, null]]]]]
Output
6
Explanation
A longest path is [4, 3, 2, 0, 6, 7]

Think about the choices you can make at any node.
Either it is at the top of the longest path or it allows another node to be at the top.
height, diameter??

Binary Tree Diameter Algorithm via DFS+BFS

We can first convert the binary trees to Graph which is stored using Adjacent List. The advantage of doing so is that we can traverse from children nodes to parent nodes as the nodes in binary tree are mapped to vertices in Graph.

We can do a Breadth First Search or Depth First Search from a random node in the Graph, and let’s say the furthest we can get to is Vertex A. And then start from Vertex A, we do the traversal (either in BFS or DFS) and we get to the furthest vertex B. The path between A and B is the longest path in the Graph (thus the Binary Tree).

class Solution:
    def longestPathInBinaryTree(self, root):
        if not root:
            return 0
        ans = 0
        G = defaultdict(list[Tree])

        def dfs(root, par):
            if not root:
                return
            if par:
                G[root].append(par)
                G[par].append(root)
            dfs(root.left, root)
            dfs(root.right, root)

        # converting binary tree to Graph G
        dfs(root, None)

        def bfs(root):
            q = deque([(root, 1)])
            seen = set([root])
            node = root
            dist = 0
            while q:
                cur, d = q.popleft()
                if d > dist:
                    node = cur
                    dist = d
                for n in G[cur]:
                    if n not in seen:
                        q.append((n, d + 1))
                        seen.add(n)
            return (node, dist)                
        node, _ = bfs(root)
        _, dist = bfs(node)
        return dist

The time and space complexity is O(N) where N is the number of the nodes in binary tree. The space is required to store the Graph (N vertex and N-1 edges). And we need to traverse twice either in DFS or BFS.

Longest Path Problems in Binary Tree

• Teaching Kids Programming – Longest Even Value Path in Binary Tree via Graph Breadth First Search Algorithm
• Teaching Kids Programming – Longest Even Value Path in Binary Tree using Recursive Depth First Search Algorithm
• Teaching Kids Programming – Longest Path in Binary Tree via Recursive Depth First Search Algorithm
• Teaching Kids Programming – Longest Path in Binary Tree via Diameter Algorithm (DFS + BFS)

–EOF (The Ultimate Computing & Technology Blog) —