Sameh.S.Hegazy
BAN USERHere is my C# implementation
static void SetGrandParent(Node n, Node parent, Node GrandParent)
{
if (GrandParent != null)
n.GrandParent = GrandParent;
if (parent != null)
{
if (n.Left != null)
SetGrandParent(n.Left, n, parent);
if (n.Right != null)
SetGrandParent(n.Right, n, parent);
}
else
{
if (n.Left != null)
SetGrandParent(n.Left, n, null);
if (n.Right != null)
SetGrandParent(n.Right, n, null);
}
}
and first Call Will be
SetGrandParent(tree, null, null);
Here is a C# Solution using LinkedList from Generic Collections
static void Main(string[] args)
{
LinkedList<int> first = new LinkedList<int>();
first.AddLast(1);
first.AddLast(2);
first.AddLast(5);
first.AddLast(8);
first.AddLast(12);
first.AddLast(16);
first.AddLast(17);
first.AddLast(22);
LinkedList<int> second = new LinkedList<int>();
second.AddLast(2);
second.AddLast(2);
second.AddLast(3);
second.AddLast(4);
second.AddLast(7);
second.AddLast(11);
second.AddLast(14);
second.AddLast(33);
LinkedList<int> mergedList = MergeSortedLinkedList(first, second);
PrintLinkedList(mergedList);
}
static LinkedList<int> MergeSortedLinkedList(LinkedList<int> FirstList, LinkedList<int> SecondList)
{
if (SecondList.First.Value >= FirstList.Last.Value)
{
FirstList.AddLast(SecondList.First);
return FirstList;
}
if (FirstList.First.Value >= SecondList.Last.Value)
{
SecondList.AddLast(FirstList.First);
return SecondList;
}
LinkedListNode<int> currentToInsert = SecondList.First;
LinkedListNode<int> lastReachedNode = FirstList.First;
while (currentToInsert != null)
{
while (lastReachedNode.Next != null && lastReachedNode.Value < currentToInsert.Value)
{
lastReachedNode = lastReachedNode.Next;
}
if (lastReachedNode.Next == null)
FirstList.AddAfter(lastReachedNode, currentToInsert.Value);
else
FirstList.AddBefore(lastReachedNode, currentToInsert.Value);
currentToInsert = currentToInsert.Next;
}
return FirstList;
}
static void PrintLinkedList(LinkedList<int> ListToPrint)
{
LinkedListNode<int> toPrint = ListToPrint.First;
while (toPrint != null)
{
Console.WriteLine(toPrint.Value);
toPrint = toPrint.Next;
}
}
here is my solution , any comments are welcomed
the basic idea is nested post order search algorithm
- Sameh.S.Hegazy September 11, 2010