## Goldman Sachs Interview Question

Software Engineer / Developers**Team:**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