Teaching Kids Programming – Longest Even Value Path in Binary Tree using Recursive Depth 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?

Recursive Depth First Search Algorithm to Compute the Longest Even Value Path in Binary Tree

We can easily traverse a binary tree using Recursive Depth First Search (pre-order, in-order, post-order etc) Algorithms. We let it return the longest even value path count that starts with the current node. If the current node is odd – then it should return zero. Otherwise, we need to store the maximum value of the longest even value path which could pass the current node.

The recursion does two things: return the longest even path starts with current node, and set the global longest even path.

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

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def longestEvenPathNodesCount(self, root):
        ans = 0
        def dfs(root):
            if not root:
                return 0
            nonlocal ans
            left = dfs(root.left)
            right = dfs(root.right)
            if root.val & 1 == 0:
                ans = max(ans, left + right + 1)
                return 1 + max(left, right)
            return 0
        dfs(root)
        return ans

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def longestEvenPathNodesCount(self, root):
        ans = 0
        def dfs(root):
            if not root:
                return 0
            nonlocal ans
            left = dfs(root.left)
            right = dfs(root.right)
            if root.val & 1 == 0:
                ans = max(ans, left + right + 1)
                return 1 + max(left, right)
            return 0
        dfs(root)
        return ans

Time and space complexity is O(N) as each node is visited only once. We can also solve this problem by treating the binary tree as a Graph: Teaching Kids Programming – Longest Even Value Path in Binary Tree via Graph Breadth 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) —