Teaching Kids Programming – Longest Even Value Path in Binary Tree via Graph Breadth First Search Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a binary tree root, return the longest path consisting of even values 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, [8, null, null], [2, [6, [4, null, null], null], [0, null, null]]]
Output
5
Explanation
A longest path is [8, 0, 2, 6, 4]

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

can the inorder traversal of tree help ?.
A similar approach to the Diameter of the tree?

Breadth First Search Algorithm to Compute the Longest Even Value Path in Binary Tree (Graph)

We can convert the binary tree into a Graph (and store the Graph in a adjacent list). Then for every even vertex in the Graph, we can perform a Breadth First Search algorithm to return the longest even node path from that node. And we can store the longest/maximum even path for the Graph.

To convert the binary tree into a Graph – we can do a Depth First Search or Breadth First Search. The following using DFS (Recursion) to convert the binary tree into a Graph (a collection of vertex and edges).

# 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):
        G = defaultdict(list)

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

        def bfs(root):
            if not root or root.val & 1:
                return 0
            ans = 0
            q = deque([(root, 1)])
            seen = set()
            seen.add(root)
            while q:
                cur, d = q.popleft()
                ans = max(ans, d)
                for c in G[cur]:
                    if c.val & 1 == 0 and c not in seen:
                        seen.add(c)
                        q.append((c, d + 1))
            return ans

        dfs(root, None)
        ans = 0      
        for i in G:
            if i.val & 1 == 0:
                ans = max(ans, bfs(i))
        return ans

We can also perform a Recursive Depth First Search algorithm on even vertex to obtain the longest even path from that node.

# 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):
        G = defaultdict(list)

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

        def dfs2(root, seen = set()):
            if not root or root in seen or root.val & 1:
                return 0
            seen.add(root)
            ans = 0
            for n in G[root]:
                ans = max(ans, dfs2(n, seen) + 1)
            return ans

        dfs(root, None)
        ans = 0      
        for i in G:
            if i.val & 1 == 0:
                ans = max(ans, dfs2(i, set()))
        return ans

Time complexity is O(N^2) as we have N vertex and for each vertex, the BFS or DFS requires O(N) time e.g. considering a linked list Graph with all even nodes.

Obviously, using the Pure DFS is more efficient: Teaching Kids Programming – Longest Even Value Path in Binary Tree using Recursive Depth First Search Algorithm

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) —