Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
2
of 2 vote

Since this is C, I'm using Java with the following redefinition.

O(n) runtime Complexity with roughly O(n) memory where m is the average number of children on each node.

class Node{
    ArrayList<Node> children;
    int val;
}

public static List<Node> get PostOrder(Node root){
    LinkedList<Node> results = new LinkedList<Node>();
    if(root == null){
        return results;
    }

    Stack<Node> unprocessed = new Stack<Node>();
    unprocessed.push(root);
    while(!unprocessed.isEmpty()){
        Node node = unprocessed.pop();
        results.addFirst(node);
        for(Node childNode : node.children){
            unprocessed.push(childNode);
        }
    }
    return results;
}

EDIT: The following was my first attempt. IT was recursive. I've since been told that 'iterative' means 'non-recursive'. Left this code for posterity

class Node{
    ArrayList<Node> children;
    int val;
}

public static ArrayList<Node> getPostOrder(Node root){
    ArrayList<Node> results = new ArrayList<Node>();
    if(root == null){
        return results;
    }

    for(Node child : root.children){
        results.addAll(getPostOrder(child));
    }
    results.add(root);
    
    return results;
}

- zortlord September 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The problem says to do it iteratively, your code has recursion..

- divm01986 September 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You implemented pre-order traversal, because parent element is added to the result before any of its children.
It should be other way around.

- damluar October 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

public class NArrTreeTraversal {

    private static class NArrTreeNode {
        int val;
        ArrayList<NArrTreeNode> children;

        public NArrTreeNode(int value) {
            val = value;
            children = new ArrayList<>();
        }
    }


    public ArrayList<Integer> postOrder(NArrTreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        HashSet<NArrTreeNode> hash = new HashSet<>();
        Stack<NArrTreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            NArrTreeNode node = stack.peek();
            if (node.children.size() == 0 || hash.contains(node)) {
                result.add(stack.pop().val);
            } else {
                node.children.forEach(n -> stack.push(n));
                hash.add(node);
            }
        }
        return result;
    }
}

- rsrs3 September 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

The order of children pushed to the stack has to be from right to left. Otherwise right-most child will be processed first.

- damluar October 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This is a tree, so no cycle. Then why set(hash) is being used here?

- infinity October 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We may add a flag for each node whether its children have been visited, like this:

void PostOrderTraverse(Node* root)
{
	if(!root) return;
	
	typedef pair<Node*, bool> PNB;
	stack<PNB> st;
	st.push(PNB(root, false));
	while(!st.empty()){
		PNB& x = st.top();
		if(x.second){//x's children have been visited, time to visit x
			cout << x.first->val;
			st.pop();
		}
		else{//x's children have not been visited, do them first
			x.second = true;//change the flag
			for(Node* p : x.first->children){//add children to stack
				st.push(PNB(p, true));
			}
		}
	}
}

- uuuouou September 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

void PostOrderTraversal(Node *node, stack<Node *> & s)  {
  for (vector<Node *>::const_iterator i = node->children.begin(); i !=  node->children.end(); ++i) {
    PostOrderTraversal(*i, s);
  }
  DoSomethingClever(node);
}

- Maxim September 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why not something simple, like this? Correct me please if I misunderstood the task.

void PostOrderTraversal(Node *node, stack<Node *> & s)  {
  for (vector<Node *>::const_iterator i = node->children.begin(); i !=  node->children.end(); ++i) {
    PostOrderTraversal(*i, s);
  }
  cout << node->val << endl;
}

- Maxim September 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi, you misunderstood that algorithm is iterative. So, no recursion

- Iuri Sitinschi September 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 4 vote

public void printPostOrder(Node n) throws NullPointerException
{
	if(n==null)
	{
		throw new NullPointerException();
	}
	Queue<Node> toVisit=new LinkedList<Node>();
	Stack<Node> toPrint=new LinkedList<Node>();
	toVisit.enqueue(n);
	while(!toVisit.isEmpty())
	{
		Node top=toVisit.dequeue();
		toPrint.push(top)
		for(int i=top.children().size()-1;i>=0;i--)
		{
				toVisit.enqueue(top.children.get(i));
			
		}
	}
	while(!toPrint.isEmpty())
	{
		System.out.print(toPrint.pop().value);
	}
}
//O(n) time complexity, O(n) space complexity where n is the number of nodes in the graph.

- divm01986 September 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I believe you should use another stack instead of queue

- Iuri Sitinschi September 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The queue to perform a BFS type traversal of the tree while simultaneously pushing a visited node into a stack. After the traversal (level wise as guaranteed by BFS) pop out all the elements in the stack this is the 'visit' part of post order which will be in reverse level order (i.e. last child will be printed first and root last) which is the expected behavior for Post Order

- PyrocasterX90 September 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

agree it should use stack to traverse nodes instead of queue. Revised above logic,
{{
void printPostOrderIterative(TreeNode* root)
{
if(!root)
return;
stack<TreeNode*> store;
stack<TreeNode*> traverse;

traverse.push(root);

while (!traverse.empty())
{
TreeNode* element = traverse.top();
store.push(traverse.top());
traverse.pop();
for (int i = element->children.size() -1 ; i >= 0; i--)
{
traverse.push(element->children[i]);
}
}

while (!store.empty())
{
printf("%d\n", store.top()->data);
store.pop();
}
}
}}

- hm September 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I must be missing something here. Where is the code that checks whether a node has already been visited - like a hash that maintains list of nodes already visisted?

- boreal September 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ah! ignore my previous post - this is an n-ary tree, not a bidirectional graph...

- boreal September 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'm wonder that what is the post order of this tree?

0
/ | \
1 2 3
/ | \
4 5 6

- malinbupt September 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.List;
import java.util.ArrayList;
import java.util.Stack;
import java.util.Arrays;

public class Node {
	
	private int val;
	private List<Node> children;
	
	public Node(int val) {
		this.val = val;
	}
	
	public void printWithIterativePostOrderTraversal() {
		Stack<Integer> print = new Stack<>();
		Stack<Node> traverse = new Stack<>();
		traverse.push(this);
		
		while (!traverse.isEmpty()) {
			Node n = traverse.pop();
			print.push(n.val);
			if (n.children != null) {
				for (Node child : n.children) {
					traverse.push(child);
				}
			}
		}
		
		while(!print.isEmpty()) {
			System.out.print(" " + print.pop());
		}
	}
		
	public void setChildren(Node... children) {
		this.children = Arrays.asList(children);
	}	
	
}

- Iuri Sitinschi September 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I know what is post order traversal, but what does it means here for n-ary tree ? I know the definition for binary tree

- jigili September 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Binary Tree = 2 children at most.
N-ary Tree = each node can have up to N children

- krutin September 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void postOrder(Node root) {

		Stack<List<Node>> stack = new Stack<>();

		Node node = root;
		List<Node> lst = null;

		while (true) {

			if(node != null) {

				lst = node.children;

				node = null;

				if(lst!=null && lst.size()>0) {

					//push the list in the stack (do not modify original tree structure).
					stack.push(new ArrayList<>(lst));

					//get first item from this list
					node = stack.peek().get(0);

				}

			} else if (!stack.isEmpty()) {

				lst = stack.pop();

				node = lst.remove(0);	//shift left

				System.out.print(node.data+" ");
				
				node = null;
				if(lst.size()>0) {
					stack.push(lst);	//push back remaining list into stack
					node = stack.peek().get(0);	//prepare for next iteration
				}

			} else {

				break;

			}

		}

		System.out.println(root.data);

	}

- kn September 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi this helped me.
Can you please help me to check if the parent node is dependent on child and throw error if so.
Thanks in advance

- sunny346 October 12, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

A working algorithm. Basically, the idea is as follows.:
- Push every node on the stack along with its index in parent's array and move to the leftmost child (or null)
- When encounter null then peek the stack and handle two cases - there are siblings on the right or there aren't (in which case print)

void traversePostOrderIterNonModifying(shared_ptr<Ntree> n)
{
	stack<pair<shared_ptr<Ntree>,int>> S;
	int curInd = 0;
	int lastInd = 0;

	shared_ptr<Ntree> cur = n;
	shared_ptr<Ntree> prev = nullptr;
	shared_ptr<Ntree> next;

	while(cur || !S.empty())
	{
		// going down
		if (cur)
		{
                        // Pick the leftmost node or null
			next = cur->children.empty() ? nullptr : cur->children[0]; 
                        // Push the current node on the stack along with its index in parent't array
			S.emplace(cur, curInd); 
			curInd = 0;
		}
		else
		{
			prev = S.top().first; 

			// Some siblings on the right
			if (!prev->children.empty() && (prev->children.size() != lastInd + 1))
			{
				curInd = lastInd +1;
				next = prev->children[curInd];
			}
			else // The prev node did not have any children or we came back from the last one
			{
				cout << prev->val << endl;
				lastInd = S.top().second; 
				S.pop();
				next = nullptr;
			}

		}
		cur = next;

	}
}

- AP September 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{postorder(tree *head){
int temp = head->children.size();
int i;
for(i=0;i<temp/2;i++){
postorder(head->children[i]);
}
for(i=temp/2+1; i<temp+1;i++){
postorder(head->children[i]);
}
cout<<head->val;
}
}}

- amit September 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{postorder(tree *head){
int temp = head->children.size();
int i;
for(i=0;i<temp/2;i++){
postorder(head->children[i]);
}
for(i=temp/2+1; i<temp+1;i++){
postorder(head->children[i]);
}
cout<<head->val;
}
}}

- amit September 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct Node {

	Node(int v) : Val(v) {}

	int Val;
	vector<Node*> Children;
};


Node *nextChild(Node *root, Node *curChild) {
	if (curChild == nullptr) {
		return root->Children.empty() ? nullptr : root->Children[0];
	}
	else {
		int i = 0;
		int n = root->Children.size();
		for (; i < n && curChild != root->Children[i]; ++i);
		return i >= n - 1 ? nullptr : root->Children[i + 1];
	}
}

void PostOrder(Node *root) {
	stack<Node*> st;
	Node *pre = nullptr;

	while (root != nullptr || !st.empty()) {
		while (root != nullptr) {
			st.push(root);
			root = root->Children.empty() ? nullptr : root->Children[0];
		}

		root = st.top();

		Node *next = nextChild(root, pre);
		if (next == nullptr) {
			cout << root->Val << "";
			pre = root;
			st.pop();
		}
		root = next;
	}
	cout << endl;
}

- malinbupt September 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <deque>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

struct Node {
        int val;
        vector<Node*> children;

        Node(int v) : val(v) {}
};

void traverseTreeRecursive(const Node *n) {
        for (auto node : n->children) {
                traverseTreeRecursive(node);
        }
        cout << n->val << " ";
}

void traverseTreeIterative(Node *n) {
        map<Node*, bool> nodeExpanded;
        vector<Node*> stack;
        stack.push_back(n);
        while (stack.size() > 0) {
                if(nodeExpanded[stack.back()]) {
                        cout << stack.back()->val << " ";
                        stack.pop_back();
                } else {
                        nodeExpanded[stack.back()] = true;
                        for (auto &ch : stack.back()->children) {
                                stack.push_back(ch);
                        }
                }
        }
}

int main() {

        Node n1(1); Node n2(2); Node n3(3); Node n4(4); Node n5(5); Node n6(6); Node n7(7);

        n1.children.push_back(&n2); n1.children.push_back(&n3); n1.children.push_back(&n4);
        n4.children.push_back(&n5); n4.children.push_back(&n6);
        n6.children.push_back(&n7);
        //1-------|-------|
        //2     3       4-------|
        //              5       6
        //                      7

        traverseTreeRecursive(&n1);
        cout << endl;
        traverseTreeIterative(&n1);
        cout << endl;

        return 0;
}

- palitsin September 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Both variants recursive and iterative for testing.
For every node keep a boolean value signing that we have pushed its children to stack already.

- palitsin September 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <deque>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

struct Node {
        int val;
        vector<Node*> children;

        Node(int v) : val(v) {}
};

void traverseTreeRecursive(const Node *n) {
        for (auto node : n->children) {
                traverseTreeRecursive(node);
        }
        cout << n->val << " ";
}

void traverseTreeIterative(Node *n) {
        map<Node*, bool> nodeExpanded;
        vector<Node*> stack;
        stack.push_back(n);
        while (stack.size() > 0) {
                if(nodeExpanded[stack.back()]) {
                        cout << stack.back()->val << " ";
                        stack.pop_back();
                } else {
                        nodeExpanded[stack.back()] = true;
                        for (auto &ch : stack.back()->children) {
                                stack.push_back(ch);
                        }
                }
        }
}

int main() {

        Node n1(1); Node n2(2); Node n3(3); Node n4(4); Node n5(5); Node n6(6); Node n7(7);

        n1.children.push_back(&n2); n1.children.push_back(&n3); n1.children.push_back(&n4);
        n4.children.push_back(&n5); n4.children.push_back(&n6);
        n6.children.push_back(&n7);
        //1-------|-------|
        //2     3       4-------|
        //              5       6
        //                      7

        traverseTreeRecursive(&n1);
        cout << endl;
        traverseTreeIterative(&n1);
        cout << endl;

        return 0;
}

- palitsin September 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void printPostOrder(Node * head) {
        stack<Node*> S;
        stack<Node*> subTreeRoots;
        S.push(head);
        while(!S.empty()) {
                Node * top = S.top();
                S.pop();
                subTreeRoots.push(top);
                vector<Node*> children = top->children;
                for(vector<Node*>::iterator i = children.begin(); i!=children.end(); i++) {
                        S.push(*i);
                }
        }

        while(!subTreeRoots.empty()) {
                Node * n = roots.top();
                roots.pop();
                cout << n->value<<", ";
        }
        cout <<endl;
}

- BuckTheTruck September 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void printPostOrder(Node * head) {
        stack<Node*> S;
        stack<Node*> subTreeRoots;
        S.push(head);
        while(!S.empty()) {
                Node * top = S.top();
                S.pop();
                subTreeRoots.push(top);
                vector<Node*> children = top->children;
                for(vector<Node*>::iterator i = children.begin(); i!=children.end(); i++) {
                        S.push(*i);
                }
        }

        while(!subTreeRoots.empty()) {
                Node * n = roots.top();
                roots.pop();
                cout << n->value<<", ";
        }
        cout <<endl;
}

- BuckTheTruck September 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def postorderIterative(root):
    temp = root
    stack = []
    index = -1
    while True:
        while temp:
            stack.append((temp,0))
            if len(temp.childs):
                temp = temp.childs[0]
            else:
                temp = None
        
        if len(stack) == 0:
            break
        
        item,index = stack.pop()
        print item.data,
        
        parent,pi = stack[-1]
        while len(parent.childs) <= index + 1:
            if len(stack) == 0:
                break
            item,index = stack.pop()
            print item.data,
            if len(stack) == 0:
                break
            parent,pi = stack[-1]
            
        if len(stack) == 0:
            break
        temp = parent.childs[index + 1]
        stack.append((temp,index + 1))
        if len(temp.childs):
            temp = temp.childs[0]
        else:
            temp = None

- Ronak Lakhwani October 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def postorderIterative(root):
    temp = root
    stack = []
    index = -1
    while True:
        while temp:
            stack.append((temp,0))
            if len(temp.childs):
                temp = temp.childs[0]
            else:
                temp = None
        
        if len(stack) == 0:
            break
        
        item,index = stack.pop()
        print item.data,
        
        parent,pi = stack[-1]
        while len(parent.childs) <= index + 1:
            if len(stack) == 0:
                break
            item,index = stack.pop()
            print item.data,
            if len(stack) == 0:
                break
            parent,pi = stack[-1]
            
        if len(stack) == 0:
            break
        temp = parent.childs[index + 1]
        stack.append((temp,index + 1))
        if len(temp.childs):
            temp = temp.childs[0]
        else:
            temp = None

- raunaklakhwani October 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <vector>
#include <queue>
#include <stack>
#include <iostream>

using namespace std;

struct Node {
	int val;
	vector<Node*> children;
};

struct onStack
{
	Node *node;
	int i;
};

void createTree(Node *head)
{
	Node *node, *qNode;
	char ch;
	queue<Node *> q;

	cout << "Enter value of head node: ";
	cin >> head->val;

	q.push(head);



	while (!q.empty())
	{
		qNode = q.front();
		q.pop();

		cout << "do you want to add child of " << qNode->val << "?" << endl;
		cin >> ch;

		while (ch == 'y' || ch == 'Y')
		{
			node = new Node();
			cout << "Enter value of head node: ";
			cin >> node->val;

			qNode->children.push_back(node);
			q.push(node);
			cout << "do you want to add another child of " << qNode->val << "?" << endl;
			cin >> ch;

		}

	}
}

//Recursive solution
void postorderRec(Node *head)
{
	if (head == NULL)
	{
		cout << "empty tree" << endl;
		return;
	}

	if (head->children.empty())
		cout << head->val << " ";
	else
	{
		for (vector<Node *>::iterator iter = head->children.begin(); iter != head->children.end(); iter++)
		{
			postorderRec(*iter);
		}
		cout << head->val << " ";
	}

}


//Iterative solution
void postorderiTer(Node *head)
{
	if (head == NULL)
	{
		cout << "empty tree" << endl;
		return;
	}

	stack <onStack *>st;
	onStack *temp = new onStack();

	temp->node = head;
	temp->i = 0;

	st.push(temp);

	while (!st.empty())
	{
		onStack *top = st.top();

		if (top->i< top->node->children.size())
		{
			temp = new onStack();
			temp->node = top->node->children[top->i];
			temp->i = 0;
			top->i = top->i + 1;

			st.push(temp);
		}
		else
		{
			st.pop();
			cout << top->node->val << " ";
		}

	}
	
}

int main()
{
	Node *head =  new Node();
	createTree(head);
	postorderRec(head);
	cout << endl;
	postorderiTer(head);
	return 0;
}

- Anonymous December 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct Node {
	int val;
	vector<Node*> children;
};

void createTree(Node *head)
{
	Node *node, *qNode;
	char ch;
	queue<Node *> q;

	cout << "Enter value of head node: ";
	cin >> head->val;

	q.push(head);



	while (!q.empty())
	{
		qNode = q.front();
		q.pop();

		cout << "do you want to add child of " << qNode->val << "?" << endl;
		cin >> ch;

		while (ch == 'y' || ch == 'Y')
		{
			node = new Node();
			cout << "Enter value of head node: ";
			cin >> node->val;

			qNode->children.push_back(node);
			q.push(node);
			cout << "do you want to add another child of " << qNode->val << "?" << endl;
			cin >> ch;

		}

	}
}

//Recursive solution
void postorderRec(Node *head)
{
	if (head == NULL)
	{
		cout << "empty tree" << endl;
		return;
	}

	if (head->children.empty())
		cout << head->val << " ";
	else
	{
		for (vector<Node *>::iterator iter = head->children.begin(); iter != head->children.end(); iter++)
		{
			postorderRec(*iter);
		}
		cout << head->val << " ";
	}

}


//Iterative solution
void postorderiTer(Node *node)
{
	if (node == NULL)
	{
		cout << "empty tree" << endl;
		return;
	}

	stack <Node *>st;
	map<Node *, int> m;
	Node *temp;
	int index;

	st.push(node);
	m.insert(pair<Node *,int>(node, 0));


	while (!st.empty())
	{
		temp = st.top();
		index = m.find(temp)->second;

		if (index < temp->children.size())
		{
			m.find(temp)->second++;
			node = temp->children[index];
			st.push(node);
			m.insert(pair<Node *, int>(node, 0));
		}
		else
		{
			st.pop();
			cout << temp->val << " ";
		}

	}
	
}

int main()
{
	Node *head =  new Node();
	createTree(head);
	postorderRec(head);
	cout << endl;
	postorderiTer(head);
	return 0;
}

- diptivs December 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Following is the method which is part of a NaryTree class which uses NaryTreeNode as the node structure given in the Question. Please comments....

void postOrderIterative(void)
	{
		NaryTreeNode<T>* temp;
		Stack<NaryTreeNode<T>> myStack;
		myStack.Push(root);
		while (!myStack.isEmpty())
		{
			temp = myStack.Peek();
			if (temp->getChildrens().size() > 0) {
				for (int i = 0; i < temp->getChildrens().size(); i++)
				{
					myStack.Push(temp->getChildrens()[i]);
				}
			}
			else
			{
				temp = myStack.Pop();
				cout << "Child: " << *(temp->getData()) << endl;
				while ( myStack.Peek() != nullptr &&
						myStack.Peek()->getChildrens().size() > 0 && 
						(myStack.Peek())->getChildrens()[0] == temp)
				{
					temp = myStack.Pop();
					cout << "Parent: " << *(temp->getData()) << endl;
				}
			}
		}
	}

- ND February 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Practice
{
    class NTreeNode
	{
		int data;
		List<NTreeNode> children;

		public NTreeNode(int data)
		{
			this.data = data;
		}

		public int getData()
		{
			return data;
		}

		public void setData(int data)
		{
			this.data = data;
		}

		public List<NTreeNode> getChildren()
		{
			return children;
		}

		public void setChildren(List<NTreeNode> children)
		{
			this.children = children;
		}

		@Override
		public String toString()
		{
			return "" + this.data;
		}
	}

	public static void main(String arr[])
	{
		// 6 -6 8 4 -12 9 -8 8
		Practice prc = new Practice();
		NTreeNode node1 = (prc).new NTreeNode(1);
		NTreeNode node2 = (prc).new NTreeNode(2);
		NTreeNode node3 = (prc).new NTreeNode(3);
		NTreeNode node4 = (prc).new NTreeNode(4);
		List<NTreeNode> children = Arrays.asList(node2, node3, node4);
		node1.setChildren(children);

		NTreeNode node5 = (prc).new NTreeNode(5);
		NTreeNode node6 = (prc).new NTreeNode(6);
		NTreeNode node7 = (prc).new NTreeNode(7);
		List<NTreeNode> children1 = Arrays.asList(node5, node6, node7);
		node2.setChildren(children1);

		NTreeNode node8 = (prc).new NTreeNode(8);
		NTreeNode node9 = (prc).new NTreeNode(9);
		NTreeNode node10 = (prc).new NTreeNode(10);
		List<NTreeNode> children2 = Arrays.asList(node8, node9, node10);
		node4.setChildren(children2);
		postOrderIterativelyNary(node1);
	}

	public static void postOrderIterativelyNary(NTreeNode root)
	{
		Stack<NEntry> stack = new Stack<NEntry>();
		Practice prc = new Practice();
		stack.push((prc).new NEntry(root, false));
		while (!stack.isEmpty())
		{
			NEntry entry = stack.pop();
			NTreeNode node = entry.node;
			if (entry.flag == false)
			{
				if (node.getChildren() == null || node.getChildren().size() == 0)
				{
					System.out.println(node.data);
				} else
				{
					stack.push((prc).new NEntry(node, true));
					List<NTreeNode> children = node.getChildren();
					for (int i = children.size() - 1; i >= 0; i--)
					{
						stack.push((prc).new NEntry(children.get(i), false));
					}
				}
			} else
			{
				System.out.println(node.data);
			}
		}

	}

	class NEntry
	{
		NEntry(NTreeNode node, boolean flag)
		{
			this.node = node;
			this.flag = flag;
		}

		NTreeNode node;
		boolean flag;

		@Override
		public String toString()
		{
			return node.toString();
		}
	}
}

- koustav.adorable August 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void postorder (Node *root) {
	if (root == nullptr)
		return;
	else {
		std::stack <std::pair <Node*, bool> > nodes_to_visit;
		nodes_to_visit.push (std::make_pair (root, false));

		while (!nodes_to_visit.empty ()) {

			Node *current_node = nodes_to_visit.top ().first;
			bool is_visited = nodes_to_visit.top ().second;
			if (!is_visited) {
				// not yet visited
				nodes_to_visit.top ().second = true;
				for (auto it = (current_node -> children).rbegin (); it != (current_node -> children).rend (); it++) {
					nodes_to_visit.push (std::make_pair (*it, false));
				}
			}
			else {
				// already visited
				nodes_to_visit.pop ();
			}
		}
	}
}

- vadimpilyugin July 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Why not something simple? Please correct me, If I misunderstood the task.

void PostOrderTraversal(Node *node, stack<Node *> & s)  {
  for (vector<Node *>::const_iterator i = node->children.begin(); i !=  node->children.end(); ++i) {
    PostOrderTraversal(*i, s);
  }
  DoSomethingClever( node );
}

- Maxim September 14, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More