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
Post a Comment