Amazon Interview Question Software Engineer / Developers

• 0

Give a non recursive algorithm that performs an inorder traversal without using a stack or any extra space.

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

Morris Traversal

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

threaded binary tree representation helps with inorder tree traversal, without stacks - at minimum storing a space for flags for left and/or right thread for avoiding endless loops.

Another implementation without using stack is by storing an additional pointer to the parent per node - which is costly.

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

Thanks to abcd, found Morris traversal on StackOverflow. Didn't expect the structure can be modified. Elegant solution.

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

How about using array to store Binary Tree instead of nodes structure. And simply display the array.. This would be your inorder traversal only.

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

Its mentioned no extra space....

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

<pre lang="" line="1" title="CodeMonkey54817" class="run-this"> public void morisTravel(Node localRoot){

Node current=localRoot;

while(current!=null){

if(current.leftChild==null){
System.out.print(current.key+ " ");
current=current.rightChild;
}
else{
// Find Inorder predecessor
Node pre=current.leftChild;
while(pre.rightChild!=null && pre.rightChild!=current)
pre=pre.rightChild;

if(pre.rightChild==null){
pre.rightChild=current; //
current=current.leftChild; // Make current to predecessor of current
}
// Restore
else{
pre.rightChild=null;
System.out.print(current.key+" ");
current=current.rightChild;
}

}
}
}</pre><pre title="CodeMonkey54817" input="yes">Its moris travel algorithm. Create link to inorder successor for each leaf node. after traversing break it.Concept of threaded binary tree.
</pre>

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

excellent!!!

Name:

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

Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

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.