argho.chatterjee.001
BAN USER- 0of 0 votes
AnswersGiven a Tree (binary and unbalanced)
- argho.chatterjee.001 in United States for Software development engineer II
Find all the nodes in that tree which are 'n' levels up the leaf node...
Eg:
A->root
A.left=B
A.right=C
B.left=D
B.right=E
C.right=F
D.right=G
then
if 'n' as described in the above problem statement, is say n=2
then
answer should be :
B(2 nodes up from G), A(2 nodes up from E & F)
hence ans is B,A
My Algo was;
1)Perform a DFS (left,middle, right)
2) when leaf node is encountered.. just move the stack pointer (without poping or jsut coy the stack of DFS to another stack and perform a real time pop operation) by 'n' times and then just print the node which it encounters.
code:
int n=2;
Stack treeStack = new Stack();
function find(){
treeStack .push(rootnode);
performDFS();
}
function performDFS(){
if(currnetnode.left==null && currentnode.right==null){
// this is a leaf node.
Stack tmpStack=copyStack(treeStack);
// hard coded logic(two pop operations) without using a loop since i am usnig n=2 in //this example
tmpStack.pop(); // pop 1st element
element = tmpStack.pop(); // print the 2nd element
print(element);
}
if(currnetnode.left!=null)
treestack.push(currentnode.left);
if(currnetnode.right!=null)
tree.stack.push(currentnode.right);
}| Report Duplicate | Flag | PURGE
Amazon Dev Lead Dev Lead Algorithm
I have rephrased the question as requested with a eg to make it clear
- argho.chatterjee.001 September 24, 2014my algo:
if(next node is a fried){
travel and add in stack
}
if(next node is enemy){
pop and go to previos friend node an calth the next path if there are more paths, else keep on poping to its previois fiend nodes)
eventually if there exists a path it will be found......
conplexity(worst case is n square)
best is (n log n)
what you suggested is only for balanced tree, the tree in question is unbalanced b-tree
- argho.chatterjee.001 September 24, 2014for balanced tree it is very simple
h=height of tree
if(n==2){
BFS and print all elements in level (h-n) level
}