Problem statement: Write a program to find the longest/maximum path in a weighted tree.
This coding question was asked in one of the coding interview rounds.
It is a tree in which every edge will be assigned with a number. It is also called edge distance between two connected nodes.
In the above tree example: The weight of the edge connecting nodes ‘A’ and ‘B’ is 4. Similarly, The weight of the edge connecting nodes ‘C’ and ‘F’ is 4.
The longest path in a weighted tree is 7 (4+3) from node ‘A’ to ‘C’ (A-C-E).
Here is a simple program to create a weighted tree and find the longest path.
#tree node class node: def __init__(self, intVal, listPtr=None): self.intVal=intVal self.listPtr=listPtr #find max path in weighted tree def maxPath(root): if root: if not root.listPtr: return root.intVal else: return root.intVal+max([maxPath(i) for i in root.listPtr]) #create weighted tree root=node(0,[node(4,[node(2)]),node(3,[node(4),node(2,[node(1)]),node(1)])]) #print maximum path of weighted tree print(maxPath(root))
node is used to save the data for each tree node.
The class variable
intVal is used to save the edge value from its parent. For example, the value of
intVal for node ‘C’ is 3, for node ‘E’ is 4 and for node ‘A’ (root node) is 0 (zero).
listPtr is the Python list object. It will save the addresses of all the child nodes.
To find the max path in the weighted tree, we are using the recursion mechanism.
You can solve these coding challenges in any programming language like C/C++, Java or Python. In other programming languages, there will be syntax differences. Logic will be the same.
In this tutorial, you learn to code for a weighted tree and find a maximum path in a weighted tree. If you have any questions or if you find any better solution, write in the comment.
Check competitive coding questions on the binary tree for practice if you are preparing for top product-based companies.