Google Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
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;
}
}
The order of children pushed to the stack has to be from right to left. Otherwise right-most child will be processed first.
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));
}
}
}
}
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;
}
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.
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
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();
}
}
}}
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?
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);
}
}
I know what is post order traversal, but what does it means here for n-ary tree ? I know the definition for binary tree
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);
}
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;
}
}
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;
}
#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;
}
#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;
}
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;
}
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;
}
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
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
#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;
}
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;
}
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;
}
}
}
}
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();
}
}
}
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 ();
}
}
}
}
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.
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
- zortlord September 14, 2015