# [Solved] Find Longest Path in a Weighted Tree | Coding Challenge

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.

#### What is the Weighted Tree?

It is a tree in which every edge will be assigned with a number. It is also called edge distance between two connected nodes.

Example:

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

#### Python Program

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

#### Explanation

The class `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).

A `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.

#### What’s Next?

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.

## 1 Comment

1. ```#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):
#checks if root is present
if root:
if not root.listPtr:
return root.intVal
else:
return root.intVal+max([maxPath(i) for i in root.listPtr])

d=node(2)
b=node(4,[d])

#children of f
h=node(1)

#children of c
e=node(4)
f=node(2,[h])
g=node(1)

c=node(3,[e,f,g])

# a is root
a=node(0,[b,c])

#print maximum path of weighted tree
print(maxPath(a))
```