Calculating the sum of all the nodes in a path which is equal to a given number in a tree and to return if such a path exists

Calculating the sum of all the nodes in a path which is equal to a given number in a tree  and to return if such a path exists


The idea is to run a recursive function and a stack to put the nodes from root to the leaf and pop one node at a time after calculating the sum if it is not equal to the supplied value.Then again put the other child node and check the sum. 

 using System;
using System.Collections.Generic;
class Node
    {
    public int data;
    public Node Left;
    public Node Right;

    public Node(int initial_value)
    {
        data=initial_value;
        Left=null;
        Right=null;
    }
   
    }

class Tree
    {
    Node top;
    int sum;
    int temp;
    Stack<int> stk;
    public Tree()
    {
    top=null;
    temp=0;
    sum=0;
    stk=new Stack<int>();
    }
    public Tree(int initial_value)
    {
    top=new Node(initial_value);
    }
   
    public Node ReturnRoot()
    {
    return top;
    }

    public void AddNode(int initial_data)
    {
    AddNodeLeftRight(ref top,initial_data);
    }

    public void AddNodeLeftRight(ref Node N,int data)
    {
    if(N==null)
    {
    Node newnode=new Node(data);
    N=newnode;
   
    }
    if(N.data<data)
    {
    AddNodeLeftRight(ref N.Right,data);
    return;
    }
    if(N.data>data)
    {
    AddNodeLeftRight(ref N.Left,data);
    return;
    }
    }

    public void inorder_traversal(Node N,ref string s)
    {
    if(N==null)
    {
    N=top;
    }
    if(N.Left !=null)
    {
    inorder_traversal(N.Left,ref s);
    s=s+N.data.ToString().PadLeft(3);
    }
    else
    {
    s=s+N.data.ToString().PadLeft(3);
    }
    if(N.Right!=null)
    {
    inorder_traversal(N.Right,ref s);
    }
    }

    public void sumtreepath(Node N,int val)
    {
   
    if(N==null)
    {
    Console.WriteLine("No Path with total value",val);
    }
    sum=sum+N.data;
    stk.Push(N.data);
    if(sum==val && N.Left==null && N.Right==null)
    {
    Console.WriteLine("Path Exist");
    foreach(int i in stk)
    {
   
    Console.Write(i+"->");
    }
    Console.WriteLine();
   
    }

    if(N.Left!=null)
    {
    sumtreepath(N.Left,val);
    }
   
    if(N.Right!=null)
    {
    sumtreepath(N.Right,val);
    }
    temp=stk.Pop();
    sum=sum-temp;
  
    }


}
class program
{
    public static void Main()
    {
    Tree mytree=new Tree();
    mytree.AddNode(10);
    mytree.AddNode(5);
    mytree.AddNode(4);
    mytree.AddNode(7);
    mytree.AddNode(12);

    string s="";
    int value_=22;
    Console.WriteLine("Inorder Traversal");
    mytree.inorder_traversal(null,ref s);
    Console.WriteLine(s);
    Node root= mytree.ReturnRoot();
    mytree.sumtreepath(root,value_);
    }
}

Comments

Popular posts from this blog

Authentication and Authorization in Web API -Part1

My Gardening Journey 6