We have already have post on various tree traversal in recursive way. Today we will cover how we can traverse a tree in iterative way.

Iterative Pre order tree traversal : For this we will be using stack to keep track of the traversed nodes

        public void iterativePreorder(TreeNode node)
        {

            bool done = false;
            Stack<TreeNode> parentStack = new Stack<TreeNode>();
            while (!done)
            {
                if (node == null && parentStack.Count() == 0)
                {
                    done = true;
                    return;
                }
                if (node != null)
                {
                    Console.Write(node.Data + " >");
                    parentStack.Push(node.Right);
                    node = node.Left;
                }
                else
                {
                    node = parentStack.Pop();
                }

            }
        }

We have already have post on various tree traversal in recursive way. Today we will cover how we can traverse a tree in iterative way.

Iterative in order tree traversal : For this we will be using stack to keep track of the traversed nodes.

        public void IterativeInorder(TreeNode node)
        {
            Stack<TreeNode> parentStack = new Stack<TreeNode>();

            bool done = false;
            while (!done)
            {
                if (node == null && parentStack.Count() == 0)
                {
                    done = true;
                    return;
                }
                if (node != null)
                {
                    parentStack.Push(node);
                    node = node.Left;
                }
                else
                {
                    var temp = parentStack.Pop();
                    Console.Write(temp.Data + " >");
                    node = temp.Right;
                }
            }
            Console.WriteLine();
        }

Given a single linked list, we have to detect loop. For this we will use two pointers called slow and fast. We will increment slow by one and fast by two. once both these pointers meet, this is the node from were loop is present

        public void DetectLoop(Node<T> node)
        {
            Node<T> slow = node;
            Node<T> fast = node;

            while (slow != fast && fast.Next != null)
            {
                slow = slow.Next;
                fast = fast.Next.Next;
                if (slow == fast)
                {
                    Console.WriteLine("Loop is detected");
                    return;
                }
            }
            Console.WriteLine("There is no loop");

        }

Today we will write a program for creating a two dimensional Array from a input file.

Steps.

1. Read input File.
2. Calculate the row and column count.
3. Read File line by line, split line by given delimiter and create two dimensional array.

C# Code

        public static int[,] Create2DMatrixFromFile(string inputFile
                                                   , char columnDelimiter)
        {

            if (File.Exists(@inputFile) == false)
            {
                throw new FileNotFoundException("Input file is not present ");
            }
            // Read All line from file

            string[] allLine = File.ReadAllLines(@inputFile);
            int rowCount = allLine.Count();

            int columnCount = allLine[0].Split(new char[] { columnDelimiter }, 
                                      StringSplitOptions.RemoveEmptyEntries).Count();

            int[,] matrix = new int[rowCount, columnCount];

            for (int rowCounter = 0; rowCounter < rowCount; rowCounter++)
            {
                string[] line = allLine[rowCounter].Split(columnDelimiter);
                for (int columnConter = 0; columnConter < columnCount; columnConter++)
                {
                    matrix[rowCounter, columnConter] = int.Parse(line[columnConter]);
                }

            }
           return matrix;

        }

input File

11,12,13,14,15
21,22,23,24,25
31,32,33,34,35
41,42,43,44,45
51,52,53,54,55
16,17,18,19,20
26,27,28,29,30
36,37,38,39,40
46,47,48,49,50

Today we have to write a program for reversing a Doubly linked list. A doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes. The beginning and ending nodes’ previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.

Source : http://en.wikipedia.org/wiki/Doubly-linked_list

Code

        public DoubleNode<T> Reverse()
        {
            DoubleNode<T> newHead = null;
            while (head != null)
            {
                DoubleNode<T> temp = head;
                head = head.Next;
                temp.Next = newHead;
                newHead = temp;
            }
            return newHead;
        }

        public static char MaximumOccurringCharacter(this string input)
        {
            SortedDictionary<char, int> charDict = new SortedDictionary<char, int>();
            int length = input.Length;

            for (int i = 0; i < length; i++)
            {
                if (charDict.ContainsKey(input[i]))
                {
                    charDict[input[i]]++;
                }
                else
                {
                    charDict.Add(input[i], 1);
                }
            }

            var max = charDict.Values.Max();
            var relevantKeys = charDict.Where(pair => max.Equals(pair.Value))
                .Select(pair => pair.Key).First();
            return relevantKeys;

        }

Test Case

Console.WriteLine(“Max occur char in string test is : ” + “test”.MaximumOccurringCharacter());

Console.WriteLine(“Max occur char in string maximum is : ” + “maximum”.MaximumOccurringCharacter());

Console.WriteLine(“Max occur char in string MaximumOccurringCharacter is : ” + “MaximumOccurringCharacter”.MaximumOccurringCharacter());

Output

Max occur char in string test is : t
Max occur char in string maximum is : m
Max occur char in string MaximumOccurringCharacter is : r

Today we have to write a program for finding the balance index in a given array. This problem can be solved on O( n ) time.

Approach 1

1. Loop Through the array and calculate the sum ,let’s assume sum is equal to arraySum.
2. Now again again iterate over array elements
   1. Calculate the sum of element say it is leftsum
   2. calculate the difference between arraySum and current Element in arraySum
   3. if arraySum is equal to leftSum, then current array index is the balance index.
3. Otherwise return –1, means balance index is not present in the array.

Code:

        public static int BalanceIndex(int[] input)
        {
            int arraySum = 0;
            int leftSum = 0;
            int balnaceIndex = -1;
            //Calculate the sum of all elements
            for (int i = 0; i < input.Length; i++)
            {
                arraySum = arraySum + input[i];
            }

            Console.WriteLine("Sum of Array Elements : " + arraySum);

            for (int i = 0; i < input.Length; i++)
            {
                leftSum = leftSum + input[i];
                arraySum = arraySum - input[i];
                if (arraySum == leftSum)
                {
                    balnaceIndex = i;
                    return balnaceIndex;
                }
            }

            if (leftSum != arraySum)
            {
                return -1;
            }
            return balnaceIndex;
        }

Test Case

private static void BalanceIndexTest()

{

    int[] arr = new int[] { -7, 1, 5, 2, -4, 3, 0,8 };

    Console.WriteLine(“Balance index for ” + string.Join(“,”, arr) + ” is : ” + ArrayProblems.BalanceIndex(arr));

    int[] arr1 = new int[] { 1, 3, 4, 6, 7, 2, 5, 9, 1, 11, 9, 6, 5, 8, 9, 1 };

    Console.WriteLine(“Balance index for ” + string.Join(“,”, arr1) + ” is : ” + ArrayProblems.BalanceIndex(arr1));

    int[] arr2 = new int[] { -7, 1, 5, 2, -4, 3, 0};

    Console.WriteLine(“Balance index for ” + string.Join(“,”, arr2) + ” is : ” + ArrayProblems.BalanceIndex(arr2));

    int[] arr3 = new int[] { -7 };

    Console.WriteLine(“Balance index for ” + string.Join(“,”, arr3) + ” is : ” + ArrayProblems.BalanceIndex(arr));

}

Output

Sum of Array Elements : 8

Balance index for -7,1,5,2,-4,3,0,8 is : –1

Sum of Array Elements : 87

Balance index for 1,3,4,6,7,2,5,9,1,11,9,6,5,8,9,1 is : –1

Sum of Array Elements : 0

Balance index for -7,1,5,2,-4,3,0 is : 5

Sum of Array Elements : -7

Balance index for -7 is : -1

Given an Array, find all the elements occurring odd number of time. All the elements are

That is all elements are positive integers.

Code

        public static void FindOddOccurrence(int[] input)
        {
            int length = input.Length;

            Console.Write("input Array is " + string.Join(",", input));
            Console.Write(Environment.NewLine);
            Console.WriteLine("Elements Occurring odd number of Times");
            for (int i = 0; i < length; i++)
            {
                input[Math.Abs(input[i])] = -input[Math.Abs(input[i])];
            }

            for (int i = 0; i < length; i++)
            {
                if (input[Math.Abs(input[i])] < 0)
                {
                    Console.Write(Math.Abs(input[i]) + ",");
                    input[Math.Abs(input[i])] = -input[Math.Abs(input[i])];
                }
            }
            Console.Write(Environment.NewLine);
        }

Test

Input Array is 1,2,3,1,3,1,6

Elements Occurring odd number of Times

1,2,6,

Input Array is 1,2,3,2,3,1,3

Elements Occurring odd number of Times

3,

Input Array is 1,2,4,6,7,8,3,2,3,1,3,4,1,3,2,2,2,2,2,4,8,3

Elements Occurring odd number of Times

1,2,4,6,7,3,

Input Array is 1,2,3,4,5,6,7,1,2,3,4,5,6,7

Elements Occurring odd number of Times

input : number of Rows

Output

         *
      *  *
   *  *  *
*  *  *  *

Code

        public static void PrintStar(int rows)
        {
        int temp=rows;
            for (int i = 1; i <= rows; i++)
            {
                for (int spacecounter = temp; spacecounter >= 1; spacecounter--)
                {
                    Console.Write("   ");
                }

                for (int starCounter = 1; starCounter <= i; starCounter++)
                {
                    Console.Write(" * ");
                }
                temp=temp-1;
                Console.WriteLine("");
            }
        }

Given a sorted array of integers and we have to find all Pythagorean triples.

Definition from Wikipedia : A Pythagorean triple consists of three positive integers a, b, and c, such that a² + b² = c². Such a triple is commonly written (a, b, c), and a well-known example is (3, 4, 5).

Code :

        public static void PythagoreanTriple(int[] input)
        {

            int length = input.Length;
            if (length < 3)
            {
                Console.WriteLine("Length of Array can not be less then 3");
                return;
            }

            for (int i = 0; i < length; i++)
            {
                input[i] = input[i] * input[i];
            }

            int leftPointer = 0;
            int rightPointer = 0;
            int temp = 0;
            for (int i = length - 1; i > 1; i--)
            {
                leftPointer = 0;
                rightPointer = i - 1;
                temp = input[i]; ;
                while (leftPointer < rightPointer)
                {
                    if (input[leftPointer] + input[rightPointer] == temp)
                    {
                        Console.WriteLine(Math.Sqrt(input[leftPointer]) + ";" 
                                                    + Math.Sqrt(input[rightPointer]) 
                                                    + ";" + Math.Sqrt(input[i]));
                        break;
                    }
                    else if (input[leftPointer] <= input[rightPointer])
                    {
                        leftPointer++;
                    }
                    else
                    {
                        rightPointer--;
                    }
                }
            }

        }

Test Case: