## Google Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
2
of 2 vote

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

Comment hidden because of low score. Click to expand.
0

Can you elaborate?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Well the recursive solution is really a stack in itself. You're pushing node pointers on the stack and popping them off with return statements.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Oh sorry, misread your post. I thought you said traverse using a stack. They wanted you to traverse without extra memory or a stack.

I'd like to hear a solution to this! :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Morris traversal

Comment hidden because of low score. Click to expand.
0

Sorry... this is a inorder traversal! :(

Comment hidden because of low score. Click to expand.
0

S 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.

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

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{
cur=stack.left;
stack=stack.right;
}
}
return res;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

Even I used parent pointer. But I am not sure how you would use Euler walk. Euler walk is supposed to traverse each edge exactly once. And in this case, you have to backtrack

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

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;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

geeksforgeeks.org/?p=6358

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

Comment hidden because of low score. Click to expand.
0

however u have to add a visited field in the node.
this can be solved only by addding parent pointer to node.
even if ur not using visited field u have to use stack..

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

Can this Morris Algo apply to pre-order and post-order traversal?

Comment hidden because of low score. Click to expand.
0
of 0 vote

<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>

Comment hidden because of low score. Click to expand.
0

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;
}
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi, I could implement Morris inorder traversal, and make the variant for pre-order; but I am not able to do for postorder. Can we stackless, non-recursive post-order traversal?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi Sir
Any body could u post code for non-recursive postorder traversal
thank you sir plz u shud do as early as possible

Comment hidden because of low score. Click to expand.
0
of 0 vote

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``````

Comment hidden because of low score. Click to expand.
0

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.