Goldman Sachs Interview Question
Software Engineer / DevelopersTeam: Strategies Group
Country: India
Interview Type: In-Person
Why use isRecursive boolean? I think it can be replaced by checking node.leftchild/rightchild. In this way, we can also avoid the stackframe class and using implicit stack class. I also donnot understand why every time we need to pop and then push, we can do this check by a single if(node!=null)
/*
* Inorder Tree Traversal without recursion and without stack
*
* Morris Traversal :
* 1. Initialize current as root
2. While current is not NULL
If current does not have left child
a) Print current’s data
b) Go to the right, i.e., current = current->right
Else
a) Make current as right child of the rightmost node in current's left subtree
b) Go to this left child, i.e., current = current->left
*
*/
public void morrisinorder(Node node){
if(node == null)
return;
Node current = node;
while(current != null){
if(current.left == null){
System.out.println(current.val);
current = current.right;
}else{
Node pre = current.left;
while(pre.right != null && pre.right !=current){
pre = pre.right;
}
if(pre.right == null){
pre.right = current;
current = current.left;
}else{
pre.right = null;
System.out.println(current.val);
current = current.right;
}
}
}
}
/*
* Inorder Tree Traversal without recursion and without stack
*
* Morris Traversal :
* 1. Initialize current as root
2. While current is not NULL
If current does not have left child
a) Print current’s data
b) Go to the right, i.e., current = current->right
Else
a) Make current as right child of the rightmost node in current's left subtree
b) Go to this left child, i.e., current = current->left
*
*/
public void morrisinorder(Node node){
if(node == null)
return;
Node current = node;
while(current != null){
if(current.left == null){
System.out.println(current.val);
current = current.right;
}else{
Node pre = current.left;
while(pre.right != null && pre.right !=current){
pre = pre.right;
}
if(pre.right == null){
pre.right = current;
current = current.left;
}else{
pre.right = null;
System.out.println(current.val);
current = current.right;
}
}
}
}
void Inorder_WORecursion(Tree *root)
{
if(root == NULL)
{
return;
}
else
{
Push(root);
}
while(top != -1)
{
if(root->Left != NULL)
{
Push(root->Left);
root = root->Left;
}
else
{
root = Pop();
printf("%d->",root->data);
if(root->Right != NULL)
{
Push(root->Right);
root = root->Right;
}
}
}
}
// Iterative Inorder
void Inorder(Node root)
{
Stack *stack = new Stack();
stack->Push(root);
Node temp = root->left;
while(true)
{
while(temp)
{
stack->Push(temp);
temp = temp->left;
}
if(stack->IsEmpty()) break;
temp = stack->Pop();
printf("%d ",temp->value);
temp = temp->right;
}
}
/* Function to traverse binary tree without recursion and
without stack */
void MorrisTraversal(struct tNode *root)
{
struct tNode *current,*pre;
if(root == NULL)
return;
current = root;
while(current != NULL)
{
if(current->left == NULL)
{
printf(" %d ", current->data);
current = current->right;
}
else
{
/* Find the inorder predecessor of current */
pre = current->left;
while(pre->right != NULL && pre->right != current)
pre = pre->right;
/* Make current as right child of its inorder predecessor */
if(pre->right == NULL)
{
pre->right = current;
current = current->left;
}
/* Revert the changes made in if part to restore the original
tree i.e., fix the right child of predecssor */
else
{
pre->right = NULL;
printf(" %d ",current->data);
current = current->right;
} /* End of if condition pre->right == NULL */
} /* End of if condition current->left == NULL*/
} /* End of while */
}
Simple Solution:
-Have a linked list where we can store nodes and a ArrayList
-Insert Root in linked list
-Insert 'Root->left' and 'Root->right' in ArrayList
-In case 'Root->left' exists insert 'Root->left' at Root's just left
-In case 'Root->right' exists insert 'Root->right' at Root's just right
-Repeat above steps for each level of tree
For Ex:
Let's say we have a tree
Inorder= D B E A F C G
Root = A
Procedure:
-Insert Root 'A' in Linked List
-Insert Roots Left 'B' and Right 'C' in ArrayList.
-Insert 'A' -> left (B) just before A
-Insert 'A' -> right (C) just after A
-Linked List is now = B A C
-Now Perform root action in all node present in Array List
-Linked List is now = D B E A F C G
public void InorderPrint(Node root)
{
Stack<Node> s = new Stack<Node>();
if (root!=null)
{
s.push(root);
while(!s.IsEmpty())
{
Node nd = s.pop();
if (nd!=null)
{
if(nd.rightchild)
{ s.push(nd.rightchild);}
s.push(nd);
if(nd.leftchild)
{ s.push(nd.leftchild);}
}
}
foreach(Node n in s)
{ print n.data; }
}
else
{ print error msg;}
}
Managing (or actually emulating) call stack explicitly;
- hakanserce January 01, 2013