## Google Interview Question

Software Engineer / DevelopersS is right. inorder or preorder doesn't differ (just the outputting order changes). the point is the same null pointers in the leaf nodes are manipulated as a stack to remember right childs that should be visited.

I hadn't heard about the Morris traversal before. Just googled about it. Interesting to know. However, I still am not sure how the solution for preorder would work. Any code pointers?

public ArrayList<Integer> preorder(TreeNode root){

ArrayList<Integer> res=new ArrayList<Integer>();

TreeNode stack=null;

TreeNode cur=root;

while(true){

TreeNode p=cur;

if(p!=null){

while(p.right!=null){

p=p.right;

}

p.right=stack;

stack=cur;

}

if(stack==null){

break;

}else{

res.add(stack.val);

cur=stack.left;

stack=stack.right;

}

}

return res;

}

keep a parent pointer in each node, then I guess preorder traversal is nothing but a special case of euler walk in a binary tree

while(cur_node!=root)

set subtree_visited=false

if(!subtree_visited&&cur_node.child)

{

while(cur_node.child)

cur_node=cur_node.child

}

else

{

print cur_node.val

if(cur_node.next_sibling)

{

subtree_visited=false

cur_node=cur_node.next_sibling;

}

else

{

subtree_visited=true

cur_node=cur_node.parent

}

}

above solution uses sibling pointer and parent pointer

As I said, the interviewer did not allow me to use a visited field in the node. In the end, I added a parent pointer to the node structure.

In the loop, I maintained a current and old pointer. Based on the old pointer, you know if you are coming from parent/left child/right child and handle the cases accordingly. If you reach a leaf or you reach a node from the right child, backtrack by old=curr; curr=curr->parent

Once we reach a leaf node, we can go to its parent and make its parent NULL. This way any node will know whether to branch left or right or to go to its parent.

```
void pre()
{
node *ptr,*current;
ptr = root;
while(ptr)
{
if(ptr->left && ptr->left->parent)
{
ptr=ptr->left;
}
else if(ptr->right && ptr->right->parent)
{
ptr=ptr->right;
}
else
{
current=ptr;
ptr=ptr->parent;
current->parent=NULL;
}
}
}
```

yes. threaded binary tree should work. however, i suspect there is still other smarter way

geeksforgeeks.org/?p=6358

This has nice code for Morris in-order traversal. It can be trivially modified to do pre-order traversal.

Solution for stackless inorder,preorder,postorder in slide 14,15,16 : http : / / gabrielistrate.weebly.com/uploads/2/5/2/6/2526487/curs8.pdf

<pre lang="c++" line="1" title="CodeMonkey31120" class="run-this">void stacklessPreorder(Node* root)

{

Node* p, *pre;

if(root == NULL) return;

p = root;

while(p != NULL)

{

if(p->left == NULL)

{ printf(" %d",p->value); p=p->right; continue;}

for(pre=p->left;pre->right != NULL && pre->right != p;pre= pre->right)

{ }

if(pre->right == NULL)

{ pre->right = p; printf(" %d",p->value);p = p->left; continue;}

else

{ pre->right = NULL; p = p->right;continue;}

}

}</pre><pre title="CodeMonkey31120" input="yes">

</pre>

static void preorder(Node root)

{

Node curr=root;

Node prv=null;

int f=1;

while(curr!=null)

{

f=0;

if(prv==null || prv.par!=curr)

{

f=1;

prv=curr;

System.out.println(curr.value);

if(curr.left!=null)

curr=curr.left;

else if (curr.right!=null)

curr=curr.right;

else curr=curr.par;

}

else if(prv==curr.right)

{

prv=curr;

curr=curr.par;

f=1;

}

else

{

f=1;

prv=curr;

if(curr.right!=null)

curr=curr.right;

else

curr=curr.par;

}

}

}

}

check this

```
preordermorrisiterative(Tnode *root) {
Tnode *current = root, *pred = NULL, *succesor = NULL;
while (current != NULL) {
if (current->left == NULL) {
printf(" %d ", current->data);
current = current->right;
} else {
pred = current->left;
while (pred->right != NULL && pred->right != current) {
pred = pred->right;
}
if (pred->right == NULL) {
pred->right = current;
//preorder
printf(" %d ", current->data);
current = current->left;
} else {
pred->right = NULL;
//inorder
//printf(" %d ", current->data);
current = current->right;
}
}
}
}
```

can we use extra space of O(1) ??

if yes, then this could be one of the solutions..

for preorder:

`void iterativePreorder(mynode *root) { mynode *save[100]; int top = 0; if (root == NULL) { return; } save[top++] = root; while (top != 0) { root = save[--top]; printf("[%d] ", root->value); if (root->right != NULL) save[top++] = root->right; if (root->left != NULL) save[top++] = root->left; } }`

similarly write for postorder and inorder

can we use extra space of O(1) ??

if yes, then this could be one of the solutions..

for preorder:

```
void iterativePreorder(mynode *root) {
mynode *save[100];
int top = 0;
if (root == NULL) { return; }
save[top++] = root;
while (top != 0) {
root = save[--top];
printf("[%d] ", root->value);
if (root->right != NULL)
save[top++] = root->right;
if (root->left != NULL)
save[top++] = root->left; } }
```

similarly write for postorder and inorder

Here is another solution (P = parent, R = right, L = left):

1.) you traverse the tree and when you see a node P with left Node just put that node on the right side - there you link P.R to the most right node from the L (L.R.R)

2.) continue this untill there are no left nodes. Here is a picture of the trees:

```
//
4
/ \
2 5
/ \ \
1 3 6
//
4
2
1 3
5
6
//
4
2
1
3
5
6
```

Here is a Java implementation:

```
public TreeNode preOrderSpecial(TreeNode root) {
TreeNode currNode = root;
while (currNode != null) {
if (currNode.left != null) {
TreeNode mostRight = getMostRightNode(currNode);
mostRight.right = currNode.right;
currNode.right = mostRight;
currNode.left = null;
}
currNode = currNode.right;
}
return root;
}
protected TreeNode getMostRightNode(TreeNode t) {
TreeNode result = t;
while (result.right != null)
result = result.right;
return result;
}
```

void preOrderNonRecursive( BSTNode* root )

{

if(!root)

return;

BSTNode* cur = root;

while(cur)

{

bool b = false;

BSTNode* pre = NULL;

if (cur->left)

{

pre = cur->left;

while(pre->right && pre->right != cur)

pre = pre->right;

if(!pre->right)

{

pre->right = cur;

b = true;

}

else

pre->right = NULL;

}

else

printf("%d\n",cur->val);

if(b)

{

printf("%d\n",cur->val);

cur = cur->left;

}

else

cur = cur->right;

}

}

why not use threading?? I believe preorder traversal can be achived using an even an right inorder threaded tree.

- Anonymous August 04, 2010