Interview Question for Software Engineer at Facebook:

test

public static void printTree (Node root) {
   ArrayList<Node> nodeArray = new ArrayList<Node>();
   nodeArray.add(root);
   printRecTree(nodeArray);
}

public static void printRecTree(ArrayList<Node> nodeArray) {

    ArrayList<Node> newNodeArray = new ArrayList<Node>();
    for (Node n : nodeArray) {
       n.printNode();
       if (n.left ! = null)
           newNodeArray.add(n.left));
      if (n.right!=null)
          newNodeArray.add(n.right);
    }
    System.out.print("\n");
    // free the memory - otherwise rec. calls keep refs alive
    for (Node n : nodeArray )
           n = null;
    if (newNodeArray ! = null)
        printRecTree(newNodeArray);
}

queue<Node*> q;
    Node* root;
    q.push(root);
    q.push(NULL);
    while (!q.empty()) {
        while (q.top() != NULL) {
            Node* a = q.top();
            q.pop();
            cout << a->data << ' ';
            if (a->left != NULL)
                q.push(a->left);

            if (a->right != NULL)
                q.push(a->right);
        }
        cout << endl;
        q.pop();
        q.push(NULL);
    }

#include <list>
#include <queue>
#include <iostream>

using namespace std;

class node
{
public:
    char k;
    list<node> descendants;
    node(char k) : k(k)
    {};
};

int _tmain(int argc, _TCHAR* argv[])
{
    queue<node> q;

    node root('a');

    node tmp('b');
    tmp.descendants.emplace_back(node('e'));
    tmp.descendants.emplace_back(node('f'));
    tmp.descendants.emplace_back(node('g'));

    node tmp2('d');
    tmp2.descendants.emplace_back(node('h'));
    tmp2.descendants.emplace_back(node('i'));
    tmp2.descendants.emplace_back(tmp);

    root.descendants.emplace_back(tmp);
    root.descendants.emplace_back(node('c'));
    root.descendants.emplace_back(tmp2);

    q.push(root);

    int currentlevel = 1;
    int nextlevel = 0;

    while (!q.empty())
    {
        // visit
        node n = q.front();

        cout << n.k;

        for(list<node>::iterator it = n.descendants.begin(); it != n.descendants.end(); it++)
        {
            nextlevel++;
            q.push(*it);
        }

        if(--currentlevel == 0)
        {
            cout << endl;
            currentlevel = nextlevel;
            nextlevel = 0;
        }

        q.pop();
    }
    return 0;
}