Microsoft Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
At first look it is a goog algorithm but what about this configuration:
12
4 8 22
1 2 5 6
For printing 12-8 you need to remove 4 from stack. For printing 12- 4 - 8 -22 -5 you need to add leaf element 8 in stack.
According to your print out, the example tree structure must be as follow:
12
/
4 - 8 - 22
/ | | | / |
1 2 3 9 18 24
Is This correct??
@Srishti
Please see comment from zprogd on June 19, 2012
the tree structure, just like that.
using no-recursive method to print it.
@yaya.
In the tree that you have mentioned nodes 1,2,3 are not connected.
But in zprogd comment they are connected.
So can you tell us what exactly was the tree given to you.
First of all we print all leaf siblings for currnet item. Then for every not leaf sibling deep to next(child) level and at the same time push every way Item to stack.
struct Item{
int data;
Item* child;
Item* right;
};
void PrintThree(Item* root){
Item* p = root;
list<Item*> ls;
print_leaf_siblings:
Item* chl = p;
while (chl) {
if (!chl->child) {
PrintLeaf(ls, chl);
}
chl = chl->right;
}
go_to_children:
if(p->child) {
ls.push_back(p);
p = p->child;
goto print_leaf_siblings;
}
go_to_right:
if (p->right) {
ls.push_back(p);
p = p->right;
goto go_to_children;
}
//pop siblings
while(ls.size() && (p == ls.back()->right)){
p = ls.back();
ls.pop_back();
}
//step level up
if (ls.size()){
p = ls.back();
ls.pop_back();
goto go_to_right;
}
}
void PrintLeaf(list<Item*>& ls, Item* p){
for (auto i = ls.begin(); i != ls.end(); ++i) {
cout << (*i)->data << " ";
}
cout << p->data << endl;
}
Here is a test for above code:
struct Item{
int data;
Item* child;
Item* right;
Item(int i) : data(i), child(0), right(0) {}
};
int main(int argc, _char* argv[])
{
Item i12(12), i4(4), i8(8), i22(22), i1(1),i2(2),i3(3), i18(18), i24(24);
i12.child = &i4;
i4.right = &i8;
i8.right = &i22;
i4.child = &i1;
i1.right = &i2;
i2.right = &i3;
i22.child = &i18;
i18.right = &i24;
PrintThree(&i12);
return 0;
}
public class Node {
int value;
Node[] childNodes;
int existedChildNodes;
int usedChildNodes;
Node(int value) {
this.value = value;
}
void addChildNode(Node childNode) {
if (childNodes == null) {
existedChildNodes = 5;
childNodes = new Node[existedChildNodes];
} else if ((usedChildNodes + 2) == existedChildNodes) {
Node[] temp = new Node[existedChildNodes];
System.arraycopy(childNodes, 0, temp, 0, usedChildNodes);
existedChildNodes = existedChildNodes + 5;
childNodes = new Node[existedChildNodes];
System.arraycopy(temp, 0, childNodes, 0, usedChildNodes);
}
childNodes[usedChildNodes++] = childNode;
}
public void showLeafPath() {
leafPath(null);
}
public void leafPath(String parentPath) {
if (usedChildNodes > 0) {
if (parentPath == null) {
parentPath = value + " ";
} else {
parentPath = parentPath + value + " ";
}
for (int i = 0; i < usedChildNodes; i++) {
Node child = childNodes[i];
child.leafPath(parentPath);
}
}
if (usedChildNodes == 0) {
if (parentPath != null) {
System.out.println(parentPath + " " + value);
}
}
}
@Override
public String toString() {
return "" + value;
}
}
public class Tree {
public static void main(String argc[]) {
Node rN = new Node(20);
Node c1 = new Node(1);
Node c2 = new Node(2);
Node c3 = new Node(3);
Node c4 = new Node(4);
Node c5 = new Node(5);
Node c6 = new Node(6);
Node c7 = new Node(7);
Node c8 = new Node(8);
Node c9 = new Node(9);
Node c10 = new Node(10);
Node c11 = new Node(11);
Node c12 = new Node(12);
Node c13 = new Node(13);
Node c14 = new Node(14);
Node c15 = new Node(15);
Node c16 = new Node(16);
Node vv1 = new Node(121);
Node vv2 = new Node(122);
Node vv3 = new Node(123);
Node vv4 = new Node(124);
Node vv5 = new Node(125);
Node vv6 = new Node(126);
c10.addChildNode(vv1);
c10.addChildNode(vv2);
c10.addChildNode(vv3);
c1.addChildNode(vv4);
c1.addChildNode(vv5);
c1.addChildNode(vv6);
vv6.addChildNode(c11);
c14.addChildNode(c12);
c15.addChildNode(c13);
c11.addChildNode(c14);
c12.addChildNode(c15);
c13.addChildNode(c16);
rN.addChildNode(c1);
rN.addChildNode(c2);
rN.addChildNode(c3);
rN.addChildNode(c4);
rN.addChildNode(c5);
rN.addChildNode(c6);
rN.addChildNode(c7);
rN.addChildNode(c8);
rN.addChildNode(c9);
rN.addChildNode(c10);
rN.showLeafPath();
}
}
is it necessary that the order of displaying path is like u mentioned?
i.e. 12, 4, 1,
12, 4, 2,
12, 4, 3,
12, 4, 8, 9,
12, 4, 8, 22, 18,
12, 4, 8, 22, 24,
if instead it can be
12, 4, 8, 22, 18,
12, 4, 8, 22, 24,
12, 4, 8, 9,
12, 4, 3,
12, 4, 2,
12, 4, 1,
then it can be done easily.
using a stack,push each of the non leaf nodes at each level frst like
push(12)
push(4)
push(8)
push(22)
when no more of level 1 child left , repeating the process for the stack top and
in case a leaf encountered print elements from stack[0] to stack[top] then the leaf node
so print(18)
print(24)
-now no more of child node(22) left so pop it
-repeat the same process for node(8),then node(4)
I think the node structure in not clear.
If there is a parent pointer exist, then using a stack for DFS and print the path after traversing reaches the leaf.
If there is only the pointer to the child, then we need a stack with pair<node, level> for document the level of tree node( which could be easily done in recursive form ), and a array for document the path.
if the traverse reaches the leaf, by assign the node the path[level], and print path
struct Node {
int data;
vector<Node*> childList;
};
void printTreeLeafPath(Node *root) {
// variable
struct Node *currNode;
int currlv;
stack< pair<struct Node*,int> > DFS_stack;
vector<int> path;
// initialize
currNode = root;
currlv = 1;
DFS_stack.push(pair<struct Node*,int>(currNode,currlv));
while(!DFS_stack.empty()) {
// access stack
currNode = DFS_stack.top().first;
currlv = DFS_stack.top().second;
DFS_stack.pop();
// erase the path
if(currlv <= (int)path.size())
path.erase(path.begin()+currlv-1,path.begin()+path.size());
path.push_back(currNode->data);
if(!currNode->childList.empty()){
for( vector<Node*>::iterator child_iter = currNode->childList.begin();
child_iter != currNode->childList.end(); child_iter++ )
DFS_stack.push(pair<Node *,int>(*child_iter, currlv+1));
}
else {
for(vector<int>::iterator path_iter = path.begin();
path_iter != path.end(); path_iter++)
cout << *path_iter << ",";
cout << endl;
}
}
}
use stack to simulate recursion
public void printPathsNoRe(){
int[] path = new int[1000];
printPathsNoRe(root, path);
}
private void printPathsNoRe(Node node, int[] path){
boolean[] flags = new boolean[20];
Stack<Node> s = new Stack<Node>();
int stackIndex = 0;
int pathLen = 0;
while(node != null || !s.empty()){
while(node != null){
path[pathLen] = node.data;
pathLen++;
if(node.left == null && node.right == null){
for(int i = 0; i < pathLen; i++){
System.out.print(path[i] + " ");
}
System.out.println();
}
s.push(node);
flags[stackIndex] = false;
stackIndex++;
node = node.left;
}
node = s.pop();
stackIndex--;
pathLen--;
if(node.right != null && flags[stackIndex]==false){
flags[stackIndex] = true;
s.push(node);
stackIndex++;
path[pathLen] = node.data;
pathLen++;
node = node.right;
}else{
node = null;
}
}
}
I request everyone to post algorithm rather than code. Most people here do not have time to go through many lines of code.
I could only think of a O(n) time and extra O(n) space complexitiy for this problem.
While performing traversal store the parent of each node in an array.
e.g
parent = new int[n];
parent[i] = j; // Means j is parent of I
Now when you reach a leaf node. Back Track this array to find the path.
I think backtracking is really straightforward.
class Solution {
private List<List<Integer>> paths = new ArrayList<List<Integer>>();
public List<List<Integer>> getPaths(Node root) {
backtrack(0, new ArrayList<Integer>(), root);
return paths;
}
private void backtrack(int level, List<Integer> path, Node current) {
if (current == null)
return;
if (current.getChildren() == null) {
List<Integer> newPath = path.clone();
paths.add(newPath);
return;
}
for (Node child : current.getChildren()) {
path.add(child);
backtrack(level+1, path, child);
path.remove(path.size() - 1);
}
}
}
When doing postorder traversal using stack, the stack always stores ancestor of the node from root till that node. this can be used to print path, when a leaf node is found. Code is written below.
#include<iostream>
#include<stack>
using namespace std;
class node{
public:
int data;
node *left, *right;
};
node *newNode(int data){
node *n = new node();
n->data = data;
n->left = NULL;
n->right = NULL;
return n;
}
void printPath(node *n){
stack<node*> s;
node *curr = n;
node *prev = NULL;
s.push(curr);
stack<node*> recStack;
while(!s.empty()){
curr = s.top();
if(!prev || prev->left == curr || prev->right == curr){
if(curr->left){
s.push(curr->left);
} else if (curr->right){
s.push(curr->right);
} else {
//cout<<curr->data<<" ";
while(!s.empty()){
node *temp = s.top();
s.pop();
recStack.push(temp);
}
while(!recStack.empty()){
node *temp = recStack.top();
recStack.pop();
cout<<temp->data<<" ";
s.push(temp);
}
cout<<endl;
s.pop();
}
}
if(curr->left == prev){
if(curr->right){
s.push(curr->right);
} else {
//cout<<curr->data<<" ";
s.pop();
}
}
if(curr->right == prev){
//cout<<curr->data<<" ";
s.pop();
}
prev = curr;
}
}
int main(){
node* root = newNode(12);
root->left = newNode(1);
root->right = newNode(5);
root->left->left = newNode(13);
root->left->right = newNode(4);
root->right->right = newNode(7);
root->right->left = newNode(9);
printPath(root);
}
1... Travel the tree in DFS while adding the node in a stack......
- student June 19, 20122... When you reach the leaf node.. print out of the elements in stack from 0 to top of stack + leaf node
3... No need to add the leaf element in the stack...
4... then keep popping out elements from stack and go on performing DFS on them...
eg.. for the given problem
push 12
push 4
then print 12-4-1 , 12-4-2, 12-4-3..... since 1,2,3 are leaf nodes ... if suppose node 1 had a child X then we would have pushed to stack and printed 12-4-1-X and then pop out 1