Amazon Interview Question
SDE1sCountry: United States
Not a o(n) solution see in recursion for traversing each node we will have linear time.
For each Node u r looping through the list which will also have o(h) time if h is the height of tree and internally String.valueOf() method will also run with linear time.
So ur code will work in linear time if height is smaller . But for larger trees it is certainly not linear.
Generate all paths
public void allPaths(Node root , Node [] path,HashMap<String ,String>cycle)
{
if(root == null)
{
for(int i=0;i<path.size();i++)
{ System.out.println("");
for(int j=i;j<path.size();j++)
{
System.out.print(path[j].ndoename + " --");
}
}
else
{
if(! cycle.containsKey(root.nodename)
{
cycle.put(root.nodename,root.nodename);
path.add(root);
allPaths(root.left ;path,cycle);
allPaths(root.right,path,cycle);
}
}
}
from Quora
Start with the root. Push root node to stack.
while(stack not empty) //i'll take top=top_of_stack
mark top as visited
if(top.left_node exists AND not_visited)
push(top.left_node)
else if(top.right_node exists AND not_visited)
push(top.right_node)
else //Leaf node
print stack
pop
O(n) Solution will be to use recursion in each node to append the path generated from it via right subtree and via left subtree in a list
- biplap January 22, 2014