CareerCup

This question is similar to the BFS question.
Just do a Breadth First Search on the Binary tree. We can get the nodes printed level by level.
The question also asks us to print the nodes level by level. In order to realize this , we can mark each node with a "level" property and check when to print new line.



struct Element {
Node *p;
int nodeLevel;
}

void PrintTree(Node *root )
{
int currentLevel = 0;
if (root == NULL) return;
Queue<Element> Q = new Queue<Element>;
Element e = new element(root, 0);
Q.push(e);
while(!Q.empty())
{
e = Q.pop();
if (e.level!=currentLevel)
{
print new line;
currentLevel = e.level;
}
print (e.p->value);
if (Q.p->left!=NULL)
{
Element left = new Element(Q.p->left, Q.p->level+1);
Q.push(left);
}
if (Q.p->left!=NULL)
{
Element left = new Element(Q.p->left, Q.p->level+1);
Q.push(left);
}
}



}

do simple level order traversal using 2 queues

If one uses additional memory in the form of a queue data structure, this problem can be solved. The basic logic is:

print_tree()
{
  num_dequed = 0;
  initialize queue;

  Enque root node;
  Print root value;
  Enque children, including NULL entries for missing children;

  while (queue not empty) {
    Dequeue a node;
    num_dequed++;

    Print node value; if Null, print blank space.
    Enque children (left child first and then right child);    

    if (num_dequed == 2) { // check diff for nary tree, n > 2
      Print new line;
      num_dequed = 0;
    }
  }
}

So, the sequence I am expecting is:
q print output
1
2,3 1
3,4,5 2
4,5,7 2 3
5,Null, 7 4
NUll, 7 4 5
7 blank
0 blank Null

class Node
{
    int n;
    Node *leftChild;
    Node *rightChild;
public:
	Node(int value=0, Node *left=0, Node *right=0)
        {n=value; leftChild=left; rightChild=right;}

    Node * getLeftChild() { return leftChild;}
    Node * getRightChild() {return rightChild;}
    int	   value(){return n;}
    void  setLeftChild(Node*  node) { leftChild=node;}
    void  setRightChild(Node* node) {rightChild=node;}
};

void printNode(Node* rt)
{
    if (!rt) return;
    else {
         //new queue
    	queue < Node * > q;   
    	q.push(rt);         //push root to the queue

        //nCurr: not for current layer; nNext for next layer
        int nCurr = 1;  // counter of nodes for this year. only one  root node;
        int nNext = 0;  // counter of nodes for next layer.

        while (!q.empty())
        {
            for (int i=0; i<nCurr; i++)
            {
              printf("%d  ", q.front()->value());

              //push next layer’s node;
              if (q.front()->getLeftChild())
              {
            	  q.push(q.front()->getLeftChild());
                  nNext++;
               }
              if (q.front()->getRightChild())
              {
            	  q.push(q.front()->getRightChild());
                  nNext++;
               }
               q.pop();       //discard the front one;

            }

            printf ("\n");             //next layer;
            nCurr = nNext;
            nNext = 0;
        }

    }

   return;

}

We can do this by having 2 queues.
Call them A and B.
First, we push root into A
i.e.

A->enqueue(root);
while (A->isEmpty() == false) {
    while ((temp = A->dequeue()) != NULL) {
        printf("%d ", temp->getData());
        if (temp->getLeft() != NULL) {
            B->enqueue(temp->getLeft());
        }
        if (temp->getRight() != NULL) {
            B->enqueue(temp->getRight());
        }
    }//end of inner while loop.
    printf("\n");
    //exchange the queue pointers.
    tempPtr = B;
    B = A;
    A = tempPtr;
}

Here is a solution that does not require extra memory. Visiting all nodes in a tree is O(n) and the depth of a balanced tree is log(n), so the average complexity is n * log(n). Worst case is O(n * n):

#include <iostream>
using namespace std;


struct TreeNode
{
    int value;
    TreeNode* left;
    TreeNode* right;

    explicit TreeNode(int v) : value(v), left(NULL), right(NULL)
    {
    }
};


TreeNode* createTestTree()
{
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);

    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    root->left->right->right = new TreeNode(7);
    return root;
}



size_t printTree(const TreeNode* node, size_t levelToPrint, size_t currentLevel = 0)
{
    if (node)
    {
        if (levelToPrint == currentLevel)
        {
            cout << node->value << ' ';
            return 1;
        }
        else if (levelToPrint > currentLevel)
        {
            return printTree(node->left, levelToPrint, currentLevel + 1) 
                 + printTree(node->right, levelToPrint, currentLevel + 1);
        }
    }
    return 0;
}


void printTree(const TreeNode* root)
{
    for (size_t levelToPrint = 0; ; ++levelToPrint)
    {
        if (printTree(root, levelToPrint))
        {
            cout << '\n';
        }
        else
        {
            break;
        }
    }
}


void main()
{
    const TreeNode* root = createTestTree();
    printTree(root);
}

Like always cristi.vlasceanu is correct.

cristi solution works like a charm. i ran it and the output is as required. thankx cristi for this nice solution.

Cristi - it would be wrong to say that there is no extra-memory in your solution. Since you have written recursive solution, there is extra stack memory used.

cristi, you saved at most n/2 space (cost of queue), but you spent n*logn time (n*n in worst case). Did you consider space is so much more precious than time?

@Anonymous : you moron, thats why his solution is out here !

//Simple and sweet
public void LevelOrderTraversal(Node Root)
{
   LinkedList<Node> Q = new LinkedList<node>();
   Q.add(root)
   while(!Q.isEmpty())
   {
          Q.add(null);
          while(Q.getFirst()!=null)
          {
             Node u = Q.removeFirst();
             System.out.print(u.data);
             if(u.left!=null)
                 Q.add(u.left);
             if(u.right!=null)
                 Q.add(u.right);
          } 
          Q.removeFirst(); 
   } 
}

Alternative Solution that uses extra memory per depth.

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;

namespace PrintTreeNodePerDepth
{
    public class TreeNode
    {
        public int value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int _value, TreeNode _left, TreeNode _right)
        {
            this.value = _value;
            this.left = _left;
            this.right = _right;
        }
    }

    class Program
    {
        static void PrintTreeNodePerDepth(TreeNode root)
        {
            if (root == null)
            {
                return;
            }

            Queue FIFO = new Queue();
            TreeNode separatorNode = new TreeNode(-1, null, null);
  
            FIFO.Enqueue(root);
            FIFO.Enqueue(separatorNode);

            while (FIFO.Count > 0)
            {
                TreeNode node = (TreeNode)FIFO.Dequeue();
                if (node.left != null)
                {
                    FIFO.Enqueue(node.left);
                }
                if (node.right != null)
                {
                    FIFO.Enqueue(node.right);
                }

                separatorNode = (TreeNode)FIFO.Peek();

                if (separatorNode != null && separatorNode.value == -1)
                {
                    FIFO.Dequeue();
                    if (FIFO.Count > 0)
                    {
                        FIFO.Enqueue(separatorNode);
                    }
                    System.Console.WriteLine(node.value.ToString());
                }
                else
                {
                    System.Console.Write(node.value.ToString());
                }
            }

            return;
        }

        static void Main(string[] args)
        {           
            TreeNode Node7 = new TreeNode(7, null, null);
            TreeNode Node4 = new TreeNode(4, null, Node7);
            TreeNode Node5 = new TreeNode(5, null, null);
            TreeNode Node6 = new TreeNode(6, null, null);
            TreeNode Node2 = new TreeNode(2, Node4, Node5);
            TreeNode Node3 = new TreeNode(3, null, Node6);
            TreeNode Node1 = new TreeNode(1, Node2, Node3);

            PrintTreeNodePerDepth(Node1);
        }
    }
}

static void printTreebylevel(TreeNode root){
		if(root == null)
			return;
		
		LinkedList<TreeNode> list = new LinkedList<TreeNode>();
		list.add(root);
		while(list.isEmpty() == false){
			int n = list.size();
			String s = "";
			while(n!=0){
				TreeNode p = (TreeNode) list.remove();
				n--;
				s = s + p.data + " ";
				if(p.left!=null)
					list.add(p.left);
				if(p.right!=null)
					list.add(p.right);
			}
			System.out.println(s);
		}
		
	}