Find longest even value path in binary tree, return length of said path, non-recursive

Question

I have to create an algorithm to find the longest path of even value in a binary tree without using recursion. For example, if my tree is the following: Binary Tree

The algorithm should return 3 as that is the length of the longest path of only even value.

Requirements:

We have two queues we can use
The path must start from the root(which we are given)

What I have in mind as of now:

Use Morris Traversal to go over the tree, but I don't know in which part of the code to do the "path search" portion
Somehow, use the queues to save the relevant nodes, q1 would represent the tempLongestPath and another one that is overallLongestPath.

But I don't have a clear idea about saving the path's length while going over the tree.

Thanks in advance for the help!

No, since it has to be from the root(which we are given), my apologies for not adding that to the question. — Mo. Mitwaly
For Morris Traversal you need to modify the tree which might break the solution path. — Sorin

Sorin Sorin · Accepted Answer · 2020-12-30T17:43:14

Run a BFS, pretend only even values are in the tree and keep track of the length.

Pseudocode:

queue.put(root)
L[root] = 1
Max_L = -1
while !Queue.empty():
   current = queue.pull()
   if (current %2 ==1): SKIP/CONTINUE

   if Max_L < L[current]:
       Max_L = L[current]
   if current.left:
      queue.put(current.left)
      L[current.left] = L[current]+1
   if current.right:
      queue.put(current.right)
      L[current.right] = L[current]+1
return Max_L

If you don't want to use an array or something sensible (i.e. dictionary) to store the lengths, you can use the second queue to keep track of them (do a put instead of assigning to L and do a pull when you pull from queue)

Find longest even value path in binary tree, return length of said path, non-recursive

1 Answers