Amazon Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
private static void inOrderTraversal(BinaryTreeNode root) {
// TODO Auto-generated method stub
Stack<BinaryTreeNode> s = new Stack<BinaryTreeNode>();
while (true) {
while (root != null) {
s.push(root);
root = root.getLeft();
}
if (s.isEmpty())
return;
root = (BinaryTreeNode) s.pop();
System.out.println(root.getData());
root = root.getRight();
}
}
public void inorder(Node n){
if(n.left != null){
inorder(n.left);
}
System.out.printlin(n.value);
if(n.right != null){
inorder(n.right);
}
}
There is a way to change a recursive method to a non-recursive method by stack!
Not considering that, I suggest this:
Node n = extractMin(root);
while(n != null){
System.out.println(n.value);
n = successor(n);
}
If you need to know how extractMin() and successor() works, let me know.
In a BST without any augmentation nor parent pointers, wouldn't this be O(n*h) time and O(h) space [implicity recursion stack] algorithm?
Once you get the min, you lose the information on the ancestors of the path to this min unless you have some sort of stack, right? Unless you have parent pointers that is.
Correct me if I'm wrong as I am not sure how you are going to implement the subroutines.
Before Algorithm I Should Say Something Here In This Recursion Stack Is Maintained By The Compiler It Intern Take care Of All The Things.Recursion Makes Coder To Do But MAke The Computer To Do More
Algorithm:
#include<stdio.h>
struct tree
{
int data;
struct tree *left;
struct tree *right;
}
main()
{
struct tree *tree1=newnode(1);
tree1->left=newnode(2);
tree1->right=newnode(3);
tree1->left->left=newnode(4);
tree1->left->right=newnode(5);
}
void inorder(struct tree *tree1)
{
if(tree1==NULL)
{
return;
}
inorder(tree1->left);
printf(" %d",tree1->data);
inorder(tree1->right);
}
struct tree *newnode(int data)
{
struct tree *tree1;
tree1=(struct tree *)malloc(sizeof(struct tree);
tree1->left=NULL;
tree1->right=NULL;
return tree1;
}
- Vir Pratap Uttam May 04, 2015