Find the maximum sum of leaf to root path in a binary tree

Given a binary tree, find the maximum sum path from a leaf to root. For example, in the following tree, there are three leaf to root paths 8->-2->10, -4->-2->10 and 7->10. The sums of these three paths are 16, 8 and 17 respectively. The maximum of them is 17 and the path for maximum is 7->10.

10
/ \
-2 7
/ \
8 -4

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace ConsoleApplication1
{
    public class Node
    {
        private Node left;
        private Node right;
        private int value;
        public Node(Node left, Node right, int value)
        {
            this.left = left;
            this.right = right;
            this.value = value;
        }
        public Node getLeft()
        {
            return left;
        }
        public Node getRight()
        {
            return right;
        }
        public int getValue()
        {
            return value;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            //Initializing the tree structure
            /*
                10
               /  \
             -2    7
             /  \     
            8   -4

            */
            Node eight = new Node(null, null, 8);
            Node minusFour = new Node(null, null, -4);
            Node minusTwo = new Node(eight, minusFour, -2);
            Node seven = new Node(null, null, 7);
            Node root = new Node(minusTwo, seven, 10);

            Hashtable ht = ConvertTreeToHashTable(root);
            Array keyArray = Array.CreateInstance(typeof(Node), ht.Count);
            Array valueArray = Array.CreateInstance(typeof(ArrayList), ht.Count);
            ht.Keys.CopyTo(keyArray, 0);
            ht.Values.CopyTo(valueArray, 0);
            int maxSum = 0; int count = 0;
            for (int i = 0; i < ht.Count; i++)
            {
                ArrayList nodeList = (ArrayList)ht[keyArray.GetValue(i)];
                //Check for leaf nodes
                if (nodeList == null)
                {
                    int tempSum = 0;
                    Node key = (Node)keyArray.GetValue(i);
                    tempSum = tempSum + key.getValue();
                    Console.Write(key.getValue() + " ");
                    while (true)
                    {
                        //Check the key against hash table values
                        int flag = -1;
                        for (int j = 0; j < ht.Count; j++)
                        {
                            if (valueArray.GetValue(j) != null && ((ArrayList)valueArray.GetValue(j)).Contains(key))
                            {
                                flag = j;
                                break;
                            }
                        }
                        if (flag != -1)
                        {
                            tempSum = tempSum + ((Node)keyArray.GetValue(flag)).getValue();
                            Console.Write(((Node)keyArray.GetValue(flag)).getValue() + " ");
                            key = (Node)keyArray.GetValue(flag);
                        }
                        else
                        {
                            break;
                        }
                    }
                    if (count == 0)
                    {
                        maxSum = tempSum;
                        count++;
                    }
                    else
                    {
                        if (tempSum > maxSum)
                            maxSum = tempSum;
                    }
                    Console.WriteLine();
                }
            }
            Console.WriteLine("Maximum sum from leaf to root = " + maxSum);
        }

        public static Hashtable ConvertTreeToHashTable(Node root)
        {
            Hashtable ht = new Hashtable();
            if (root != null)
            {
                Queue q = new Queue();
                q.Enqueue(root);
                while (q.Count != 0)
                {
                    Node temp = (Node)q.Dequeue();
                    ht.Add(temp, null);
                    ArrayList nodeList = new ArrayList();
                    if (temp.getLeft() != null)
                    {
                        nodeList.Add(temp.getLeft());
                        ht[temp] = nodeList;
                        q.Enqueue(temp.getLeft());
                    }

                    if (temp.getRight() != null)
                    {
                        nodeList.Add(temp.getRight());
                        ht[temp] = nodeList;
                        q.Enqueue(temp.getRight());
                    }
                }
                return ht;
            }
            return null;
        }
    }
}

Output
======
7 10
-4 -2 10
8 -2 10
Maximum sum from leaf to root = 17
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s