[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 the number. It is also called as edge distance between two connected nodes.

Example:

weighted tree data structure

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

Output:

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

Aniruddha Chaudhari

I am complete Python Nut, love Linux and vim as an editor. I hold a Master of Computer Science from NIT Trichy. I dabble in C/C++, Java too. I keep sharing my coding knowledge and my own experience on CSEstack.org portal.

Your name can also be listed here. Got a tip? Submit it here to become an CSEstack author.

Comments

Anurag Aravind Gharat

March 21, 2021 at 12:26 pm

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