Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
1. Take an array which will contain the pointer of nodes of tree.
2. Start with the index [1] of the array and put the pointer of root , i.e ar[i] = root;
3. if node has left child put ar[2*i] = node-> leftchild; if node has right child put ar[2*i + 1] = node-> rightchild;
4. repeat step 3 for every node.
5. now from the last index of the array repeat the following step
6. if(ar[i]==null) i-- ; continue;
7. if ar[i] contains the pointer of leaf node ; (ar[i]) -> leftchild == NULL && (ar[i])-> rightchild == NULL; j=i;
8 while(j !=0) { print(ar[j] -> data); j= j/2}
Can you give programming example for this ?
Especially how to repeat step 3 without using recursion.
But this is still the additional array you are talking about. If the tree is having too many nodes, the cost will be still high.
If the question is about binary tree,you can do a level order traversal with some modification.
public class Tree
{
public Tree left;
public Tree right;
public int val;
}
public class TreeNodePath
{
public TreeNodePath(Tree node,StringBuffer path)
{
this.node=node;
this.path=path;
}
public Tree node;
public StringBuffer path;
}
public static void printAllPathToLeafNonRecursive(Tree root) {
if (root == null) {
return;
}
Queue<TreeNodePath> q = new LinkedList<>();
TreeNodePath treeNodePath=new TreeNodePath();
treeNodePath.node=root;
treeNodePath.path=new StringBuffer(root.val);
q.add(treeNodePath);
while(!q.isEmpty()){
TreeNodePath pathNode=q.poll();
Tree root1 = pathNode.node;
StringBuffer currPath= pathNode.path;
if(root1.left==null && root1.right==null){
System.out.println(currPath.toString());
continue;
}
if(root1.left!=null){
StringBuffer newPath= currPath.append(",").append(root1.left.val);
q.add(new TreeNodePath(root1.left,newPath));
}
if(root1.right!=null){
StringBuffer newPath= currPath.append(",").append(root1.right.val);
q.add(new TreeNodePath(root1.right,newPath));
}
}
}
First of all I apologize for being late. I was out for a while.
We will use a stack for DFS instead of recursion. You can find out more about iterative DFS at Wikipedia.
Whenever we reach the target node, we stop the DFS right there, and start popping nodes out of a stack and construct the path, like in the code below:
// This code is for the stage after halting the DFS
// cur is the current node. It is the target node at the beginning
// DFSStack is our stack
// ans is the path
node * cur = DFSStack.top();
DFSStack.pop();
list <node *> ans;
ans.push_front(cur);
node *tmp;
while(!(DFSStack.empty()))
{
tmp = DFSStack.top();
DFSStack.pop();
if(tmp->left == cur || tmp->right == cur)
{
cur = tmp;
ans.push_front(cur);
}
}
By randomized I mean to visit children of any node in a random order, in order to have an acceptable performance for any test case. That is, when a mean adversary queries the last leaf every time, on average, we will be searching half of the tree. By doing this, our space usage will decrease a bit for the worst case :-)
You will need to have a stack and a completed array. completed array denotes if you have seen both the children of the tree.
Now push a node in the stack and increment its children count. when the completed count is 2 you can pop out the node.
The code can be written as:
void printpath()
{
int i=0;
for(i=0;i<in;i++)
printf("%d\t",stack[i]->val);
printf("\n");
}
void allpaths(struct tnode *root)
{
int done=0;
int completed[100];
int i=0;
for(i=0;i<100;i++)
completed[i]=0;
struct tnode *cur = root;
while(done!=1)
{
if(cur!=NULL)
{
push(cur);
completed[cur->val]++;
cur = cur->left;
}
else
{
cur = front();
while(cur != NULL && completed[cur->val]==2)
{
if(cur->left==NULL && cur->right==NULL)
printpath();
pop();
cur = front();
}
if(cur!=NULL)
{
completed[cur->val]++;
cur = cur->right;
}
else
done =1 ;
}
}
}
void paths(struct tnode *root,int num)
{
int done=0;
int complete[100];
int i=0;
for(i=0;i<100;i++)
complete[i]=0;
struct tnode *cur = root;
while(done != 1)
{
if(cur!=NULL)
{
push(cur);
if(cur->val==num)
break;
complete[cur->val]++;
cur = cur->left;
}
else
{
cur = front();
while(cur != NULL && complete[cur->val]==2)
{
pop();
cur = front();
}
if(cur != NULL)
{
complete[cur->val]++;
cur = cur->right;
}
else
done = 1;
}
}
if(done==0)
printpath();
}
where we have to find path from root to num.
If you perform a slight modification on the nodes of your tree, you could store both the data and the level (depth) of the node
{
struct node
{
int data;
int level;
node* p_left;
node* p_right;
};
}
Once you have your tree built and having in mind that each node stores its level, you could perform an iterative preorder traversal. Once you find the desired value, you return from the function:
{
void preOrder(node * root, int value, int * path, int & level)
{
if(root == NULL)
return;
stack<node*> s;
s.push(root);
while(!s.empty())
{
node * aux = s.top();
s.pop();
path[aux->level] = aux->data;
if(aux->data == value)
{
level = aux->level;
return;
}
if(aux->p_right != NULL)
s.push(aux->p_right);
if(aux->p_left != NULL)
s.push(aux->p_left);
}
}
}
The rest is just cout'in the path array from 0 to level
Assuming it is a BST that was asked for:
void printRootToLeafPathWithoutRecursion(node *root,int n)
{
if(root==NULL)
{
cout<<"Sorry! The node you searched for doesn't exist.";
return;
}
else
{
node *currentNode;
currentNode=root;
while(currentNode!=NULL)
{
if(n==currentNode->info)
{
cout<<currentNode->info<<"-";
return;
}
else if(n<currentNode->info)
{
cout<<currentNode->info<<"-L-";
currentNode=currentNode->left;
}
else if(n>currentNode->info)
{
cout<<currentNode->info<<"-R-";
currentNode=currentNode->right;
}
}
cout<<"Sorry! The node you searched for doesn't exist.";
}
}
You can maintain a stack implemented via doubly ll and perform a preorder
Traversal on the tree and populate the stack with the visited node. When
You reach a leaf node in preorder traversal, print the complete stack and then
Continue with the preorder traversal.
Note: the tail of the ll should have the top pointer.
Maintain a separate head pointer for the head of ll.
boolean isLeaf(Node<T> root2) {
return root2.getLeftNode()==null && root2.getRightNode() == null;
}
void printAllPathRecursive(Node<T> root,String path) {
if(root!=null && isLeaf(root)){
System.out.println(path+","+root.getData());
return;
}else{
if(root.getLeftNode()!=null)
printAllPathRecursive(root.getLeftNode(),path+","+root.getData());
if(root.getRightNode()!=null)
printAllPathRecursive(root.getRightNode(),path+","+root.getData());
}
}
boolean isLeaf(Node<T> root2) {
return root2.getLeftNode()==null && root2.getRightNode() == null;
}
void printAllPathRecursive(Node<T> root,String path) {
if(root!=null && isLeaf(root)){
System.out.println(path+","+root.getData());
return;
}else{
if(root.getLeftNode()!=null)
printAllPathRecursive(root.getLeftNode(),path+","+root.getData());
if(root.getRightNode()!=null)
printAllPathRecursive(root.getRightNode(),path+","+root.getData());
}
}
Algorithm :-
1.)Start from the root node of the tree.
2.)If the node has left child , store the node in a stack ,mark its right as unvisited in another stack and move to its left . Continue this step until you can find a left child.
3.)Now mark the current node's right child as visited and move to the right child. If the right child is empty , print the content of the stack , else go to step 2.
void root2leaf(node* tree){
struct stack{
node* arr[100];
int visited[100];
int tos;
};
stack st;
st.tos = -1;
do{
while(tree!='\0'){
st.arr[++st.tos]=tree;
st.visited[st.tos]=0;
tree=tree->left;
}
tree=st.arr[st.tos];
st.visited[st.tos]=1;
tree=tree->right;
if(tree=='\0'){
for(int i=0;i<=st.tos;i++){
printf("%d ",st.arr[i]->info);
}
printf("\n");
st.tos-=1;
while(st.visited[st.tos]==1){
st.tos-=1;
}
}
}while(st.tos!=-1);
}
Algorithm : Based on similar concept of recursion , recursion requires internal stack , I used an explicit stack to cover that feature.
Code is self explanatory. see comments
void printroot2leaf(struct tnode *root){
vector<tnode*>vb;
stack<tnode*>st;
st.push(root);
while(!st.empty()){
struct tnode* curr=st.top();
st.pop();
vb.push_back(curr);
if(isleaf(curr)){
for(int i=0;i<vb.size();i++)
cout<<vb[i]->data<<' ';
cout<<endl;
}
if(curr->right)
st.push(curr->right);
if(curr->left)
st.push(curr->left);
/*this step removes the node from vector if stack's top is not its left or right child .. trace manually for a proper understanding of this step. */ while(!vb.empty()&&!st.empty()&&!vb[vb.size()-1]->left==st.top()||vb[vb.size()-1]->right==st.top()))
vb.pop_back();
}
}
{
void paths(struct Node *root)
{
struct Node *current = root;
struct Stack *s = NULL;
bool done = 0;
while (!done)
{
if(current != NULL)
{
push(&s, current);
current = current->left;
}
else
{
if (!isEmpty(s))
{
current = pop(&s);
printStack(s); >>>> Prints current stack.
current = current->right;
}
else
done = 1;
}
}
}
}
void printRootToLeafSumWithoutRecursion(TreeJ root){
int sum=0;
Stack<TreeJ> st=new Stack<TreeJ>();
TreeJ temp=new TreeJ(0);
st.push(temp);
st.push(root);
while(st.isEmpty()==false){
TreeJ popVal1=st.pop();
TreeJ popVal2=st.pop();
temp=popVal2;
while(popVal1!=null){
temp.val=(Integer)temp.val+(Integer)popVal1.val;
if(popVal1.right!=null){
st.push(new TreeJ(temp.val));
st.push(popVal1.right);
}
popVal1=popVal1.left;
}
System.out.println(temp.val+",");
}
}
create a struct which contains tree node and information if left is traversed, right is traversed or not.just traverse the tee. add each node in stack and also keep the path in a string.
code
struct stack_node
{
tree *p;
int nlr; //visited none =-1, left =0 right =1 (can use two bools instead)
stack_node(tree *p, int nlr){this->p= p; this->nlr=nlr;};
};
void print_all_path_iter(tree *p)
{
if(!p)
return;
if(!p->left && !p->right)
{
cout<<p->val;
return;
}
std::string path="";
int path_len=0;
std::stack<stack_node *> stck;
//push root
stck.push(new stack_node(p, -1));
path= path+ p->val;//assuming p->val is string
path_len++;
while(stck.empty()==false)
{
stack_node* S= stck.top();//dont pop
//check if this is leaf
if(S->p->left == false && S->p->right == false)
{
cout<<"\n"<<path.substr(0,path_len-1);//if leaf print the substring of path
stck.pop();
delete S;
path_len--;
}
//check if none is visited
else if(S->nlr== -1)
{
if(S->p->left != null)
{
stck.push(new stack_node(S->p->left, false));
S->nlr=0;//change state of left visited
path.at(path_len)=S->p->left->val;
path_len++;
}
else
{
stck.pop();
delete S;
path_len--;
}
}
//check if left is visited
else if(S->nlr == 0)
{
if(S->p->right != null)
{
stck.push(new stack_node(S->p->right, false));
S->nlr= 1;
path.at(path_len)=S->p->right->val;
path_len++;
}
else
{
stck.pop();
delete S;
path_len--;
}
}
//check if right is visited
else if(S->nlr == 1)
{
stck.pop();
delete S;
path_len--;
}
}
return;
}
This function will print each node without recursion
/* 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;
}
// MAGIC OF RESTORING the Tree happens here:
/* 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 */
}
Your can use a single queue to print a tree. The idea is to push the node value in queue until the node's children are read. Once added to queue, add a null to mark end of that level. Hope this helps.
public int printTreeInLine(Tree root){
Queue<Tree> q = new LinkedList<>();
if(root == null)
return 0;
q.add(root);
q.add(null);
int level = 0;
while(!q.isEmpty()){
Tree temp = q.poll();
if(temp == null){
if(!q.isEmpty()){
q.add(null); //To mark new level
level++;
System.out.println();
}
}
else{
//Printing Node value in tree
System.out.print(temp.getData()+" ");
if(temp.getLeft() != null){
q.add(temp.getLeft());
}
if(temp.getRight() != null){
q.add(temp.getRight());
}
}
}
return ++level;
}
class NodePath(object):
def __init__(self, node, path):
self.cnode = node
self.cpath = list(path)
def printAllRootToLeaf(root):
path = []
stack = []
stack.append(NodePath(root, path))
while(len(stack) != 0):
pnode = stack.pop()
node = pnode.cnode
pnode.cpath.append(node)
if node.left == None and node.right == None:
out = str(pnode.cpath[0].data)
for i in pnode.cpath[1:]:
out += "-" + str(i.data)
print out
if node.left != None:
stack.append(NodePath(node.left, pnode.cpath))
if node.right != None:
stack.append(NodePath(node.right, pnode.cpath))
Can be done similar to iterative post order as follows
Stack st;
Node n = root;
while(st.size() > 0){
if( n!= null)
{
st.push(n);
n = n.left;
} else {
node t = st.peek();
if(t.right == null) // leaf found
{ print stack so far at this point
printStack();
st.pop();
// now remove the nodes from stack which are parents of this node
while( st.peek.right == t)
{
t = st.pop();
}
} else {
node = t.right;
}
}
}
This problem can be solved using the iterative method. Only a stack is needed. Here is my code for this problem and works completely fine.
class Node{
Node left, right;
int data;
Node(int x){
data=x;
}
}
public class BinaryTreeIteratorMc {
Node root;
void InOrder(){
Stack<Node> stack=new Stack<Node>();
Node n=root;
if(n==null)
return;
while(n!=null){
stack.push(n);
n=n.left;
}
while(stack.size()>0){
n=stack.pop();
System.out.print(n.data+" ");
if(n.right!=null){
n=n.right;
//System.out.println("in if");
while(n!=null){
//System.out.println("in while");
stack.add(n);
n=n.left;
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
BinaryTreeIteratorMc tree=new BinaryTreeIteratorMc();
tree.root=new Node(1);
tree.root.left=new Node(2);
tree.root.right=new Node(3);
tree.root.left.left=new Node(4);
tree.root.left.right=new Node(5);
tree.root.right.right=new Node(6);
System.out.println("Inorder traversal is :");
tree.InOrder();
}
}
void printRootToLeaf(node *new_node){
node *my_array[10];
int i = 0, num_leaf = 0;
enqueue(new_node);
while(front != NULL){
while(front->tree_node->left != NULL || front->tree_node->right != NULL){
if(front->tree_node->left != NULL){
enqueue(front->tree_node->left);
}
if(front->tree_node->right != NULL){
enqueue(front->tree_node->right);
}
dequeue();
}
my_array[i] = front->tree_node;
i++;
dequeue();
}
num_leaf = i;
i = 0;
while(i < num_leaf){
printf("\nPath %d : \n",i+1);
new_node = root;
while(new_node->val != my_array[i]->val){
printf("\n%d\n",new_node->val);
if(my_array[i]->val < new_node->val){
new_node = new_node->left;
}
else{
new_node = new_node->right;
}
}
if(new_node->val == my_array[i]->val){
printf("\n%d\n",new_node->val);
}
i++;
}
}
We can do a level order traversal which requires a queue and does not require a recursion to print all the nodes.
1. Enqueue the root node in the queue.
2. Dequeue the queue and visit it (do the necessary operation)
3. If the node has children enqueue it.
Continue step 2 and 3 until the queue is empty.
public static void levelorder(Node n) {
Queue<Node> nodequeue = new LinkedList<Node>();
if (n != null)
nodequeue.add(n);
while (!nodequeue.isEmpty()) {
Node next = nodequeue.remove();
System.out.print(next.data + " ");
if (next.getLeft() != null) {
nodequeue.add(next.getLeft());
}
if (next.getRight() != null) {
nodequeue.add(next.getRight());
}
}
}
getLeft and getRight are defined in Node class
i think it can be done using a similar concept of inorder traversal using stack(without recursion).
- LPOOK May 03, 2014