manjesh.bits
BAN USERgood soln :)
- manjesh.bits February 04, 2011Just Remove else from your first code and write last statement without else!!!
Find(Node n,Node req){
if(n==null)
return false;
if(req==A)
if(n==A)
return Find(n,B);
if(req==B)
if(n==B)
return Find(n,C);
if(req==C)
if(n==C)
return true;
return Find(n.left,req)||Find(n.right,req);
}
Do the BFS and update nodes position like This
Node Position = (parent position , current node position)
a ---- 0, 1
b ---- 1,2
c ---- 1,3
d ---- 1,2,4
e ---- 1,2,5
f ---- 1,3,6
g ---- 1,3,7
Now just ignore the last comma separated values for every node and complete the matrix as shown below
a b c d f g
a 0 0 0 0 0 0
b 1 0 0 0 0 0
c 1 0 0 0 0 0
d 1 2 0 0 0 0
e 1 2 0 0 0 0
f 1 0 3 0 0 0
g 1 0 3 0 0 0
Finally replace all none zero number to 1.
- manjesh.bits February 02, 2011Do the BFS and find the required deepest Node Pointer.
If Once you found the deepest node then find the path between root to deepest Node.
void findPath(Node root, Node node){
Stack->push(root);
if(node == root){
print stack data;
return;
}
if(root->left != null){
findPath(root->left, node);
}
if(root->right!=null){
findPath(root.right, node);
}
Stack->pop();
}
@All above,
Please follow the question correctly.. Question is related to finding "PATH" and you all people are just trying to find position(depth) of deepest 1.
One Simple Approach with time Complexity O(N*K)
RotateByK(int Arr[]){
int i=0;
for(i=0; i<K; i++){
int key = Arr[n];
ShiftArray(Arr,0,n);
Arr[0]=key;
}
}
But this is not a optimal solution .. we can optimized this solution by just jumping k elements for example the last element will be replaced by Kth element directly and so on.
Modified approach will take O(N)
- manjesh.bits January 13, 2012