CareerCup

We can store each level in the form of a linked list,each node will have 2 pointers,next and child...next will point to the next sibling in the same level,child will point to the starting point of child linked list....

Design the tree node as

public class Node {
		int value;
		LinkedList<Node> children = new LinkedList<Node>();
	}

For the level order traversal, we do not have to store the nodes in a queue we just need to store the head of the children linked list.

We can do depth limited Depth First Search.
We iterate from 1-depth. And print all elements with that particular depth.

You might think that the complexity is going to be high. But no. When the tree isn't sparse, the number of children in nth level is equal to the number of elements from level 1-(n-1). So the complexity is just getting doubled. Not more.

Asymptotically it is still same as DFS/BFS.

We can follow naive algorithm to print kth level using recursion...but this will increase complexity to n^2...any better approach??

We can use vector class

class Vector
    {
        public Node[] child = new Node[1];
        public int count = 0;

        public void add(string name)
        {
            if (count < child.Length)
            {
                child[count++] = new Node(name);
            }
            else
            {
                resize();
                child[count++] = new Node(name);
            }
        }
        public void delete(int index)
        {
            Node[] tmp = new Node[1];
            count = 0;
            for (int i = 0; i < child.Length; i++)
            {
                if (i != index)
                {
                    tmp[count++] = child[i];    
                }
            }
            child = tmp;
        }

        public void resize()
        {
            Node[] tmp = new Node[child.Length * 2];
            for (int i = 0; i < child.Length; i++)
            {
                tmp[i] = child[i];
            }
            child = tmp;
        }
        public void travers()
        {
            for (int i = 0; i < count; i++)
            {
                Console.Write(child[i].name + " ");
            }
            Console.WriteLine();
        }
    }

    class Node
    {
        public string name;
        public Node parent;

        public Node() { }
        public Node(string name) { this.name = name; }
    }

we can't use extra storage, so how about this:

public class Node
{
    Node levelFirst; //1st node of every level
    Node next; //sibling of every node
    Node parent;
    int value;
}

Now just do a level order traversal. Lots of edge cases - how do you detect that the level is done. Keep track of 1st node of every level, as you'll need to come back to it, once every level is done, to start the next level.