Tree traversal

If you will be asked in an interview to traverse a tree most likely it will not be depth first or breadth first but rather it will be a special traversal. You will be given a hierarchical table with ID's and parent ID's like the following table for instance.
The table below indicate that the first two nodes has no parent for instance, and then few nodes are under one of them and so on.

ID	ParentId	Name
5	null	Grandfather
8	null	Grandmother
7	5	son 1
4	5	daughter
2	5	son 2
3	7	grandchild

and then you will be asked to print the above nodes as follows
-Grandfather
        -Son 1
                -Grandchild
        -daughter
        -Son 2
-Grandmother

Here is the solution with explanation

class Program

    {

        static void Main(string[] args)

        {

            var n = MakeModel();// Make the model  

            PrintNode(n, new Customer{ID = -1, ParentId = null, Name = "-1"}, -1); 

            //Pass one node that can combine the root nodes under it

            Console.ReadKey();

        }

        private static void PrintNode(List<Customer> nodes, Customer n, int dept)

        {

            //Algorithm

            //When readhing a node, immediately print it

            //Get all children for the current node and recursively call the same method passing a child node at a time

            //each time you go one level deeper increase a the depth variable that maintaines 

            //how deep in the tree you are now

            if (dept >= 0) Console.WriteLine( new String('\t', dept) + "-" +  n.Name);

            var children = nodes.Where(x => x.ParentId == n.ID).ToList();

                foreach (var child in children)

                    PrintNode(nodes, child, dept + 1);

                    //Code here will execute on the way back

        }

        private static List<Customer> MakeModel()

        {

            var output = new List<Customer>

            {

                new Customer {ID = 5, ParentId = -1, Name = "Grandfather"},

                new Customer {ID = 8, ParentId = -1, Name = "Grandmother"},

                new Customer {ID = 7, ParentId = 5, Name = "Son 1"},

                new Customer {ID = 4, ParentId = 5, Name = "daughter"},

                new Customer {ID = 2, ParentId = 5, Name = "Son 2"},

                new Customer {ID = 3, ParentId = 7, Name = "Grandchild"}

            };

            return output;

        }

        

    }

    public class Customer

    {

        public int ID { get; set; }

        public int? ParentId { get; set; }

        public string Name { get; set; }

    }

Merge two sorted arrays

//Given two sorted integer arrays A and B, merge B into A as one sorted array.

            //example 1346789

            //        35689  

            var arr1 = new List<int> { 4,5 };

            var arr2 = new List<int> { 1,2,3 };

            //Loop length of arr1 - start 0 untill end of array - p = index

            //Optimization use shortest array 

            //Pick element at p, compare it with all elements in arr2 - Loop Arr2 start from last point examined

            //if arr1 Element <= arr2 element and < arr2

            //insert arr1 element left of arr2 element, otherwise keep going

            var r2 = arr2.Count;

            for (int p = 0; p < arr1.Count; p++)

            {

                for (int j = 0; j < r2; j++)

                {

                    if (arr1[p] <= arr2[j])

                    {

                        arr2.Insert(j, arr1[p]);

                        r2 = arr2.Count;

                        break;

                    }

                    if (j == r2-1) //Last item in arr2 and loop did not break above

                    {

                        arr2.Add(arr1[1]);

                        r2 = arr2.Count;

                    }

                }

            }

Insertion Sort

 var arr = new List<int> { 5,6,1,2,3,1 };// input.ToCharArray().Cast<int>().ToList();

            //Loop length of array - start from second position

            

            //Compare pointer to previous item

            //make smaller to the left untill you reach the beginning of the array

            var currentItem = 0;

            for (int p = 1; p < arr.Count; p++)

            {

                currentItem = arr[p];

                //Loop from current p position to beginning of array - pointing at location of comparison with current item and potential location of currentItem

                //If currentItem is smaller then swap 

                for (int i = p - 1 ; i >= 0; i--)

                {

                    if (currentItem < arr[i])

                    {

                        var temp = arr[i];

                        arr[i] = currentItem;

                        arr[i+1] = temp;

                    } 

                    else

                    {

                        break;

                    }

                }

                

            }