Amazon Interview Question
0of 0 votesFind the longest Zig-Zag path in a Binary TREE
Country: India
Longest Zig Zag path = Diameter of tree
There are two ways to solve this
1.)Calculate DFS to furthest node. From furthest node, recompute DFS for longest path
2.)
ll = Calculate diameter of left sub tree
lr = Calculate diameter of right subtree
ld = Calculate Height of left + right sub tree + 1
calculate max of above quantities in a recursive manner
Though I am not clear about what exactly is a zigzag path, I don't think the longest zigzag path is same as the diameter as the diameter of a tree is the number of nodes on the longest path between two leaves in the tree whereas the longest zigzag path according to me has to start from a node and go down to a leaf or maybe stop even before reaching a leaf.
i think longest zigzag path would that path in binary tree.. = longest zigzag path in left subtree from root to leaf + longest zigzag path in right subtree from root to leaf.
which would be something like that =LRLRLRLRLR +RLRLRLRLRL
can any one tell me .. that this would be also zigzag path in tree like LLLRRLRLR
or LLLLLLLRRRRLLL or not.
int zig_zag(Node n, char dir)
{
if (n==NULL)
return 0;
else if(dir=='l')
return 1 + zig_zag(n->left, 'r');
else
return 1 + zig_zag(n->right, 'l');
}
void max_zig_zag(Node *root)
{
int l, r;
l = zig_zag(root->left, 'r');
r = zig_zag(root->right, 'l');
if(l>r)
cout<<l+1<<endl;
else
cout<<r+1<<endl;
}
will it take care of the zig zag in the middle of the tree.
LR-RLRLRLRLRLRLRLRLRL
|
for example here it breaks but RLRLRLRLRLRLRLRLRL is the longest zigzag
//Here max is the longest zigzagpath length
static Integer longestZigZagPath(BinaryNode root,String type,Integer length){
if(type == null){
longestZigZagPath(root.right, "L", 1);
longestZigZagPath(root.left, "R", 1);
}
if("R".equalsIgnoreCase(type)){
if(root.right != null)
longestZigZagPath(root.right, "L", length+1);
else if(max < length)
max = length;
if(root.left != null)
longestZigZagPath(root.left, "R", 1);
}
if("L".equalsIgnoreCase(type)){
if(root.left != null)
longestZigZagPath(root.left, "R", length+1);
else if(max < length)
max = length;
if(root.right != null)
longestZigZagPath(root.right, "L", 1);
}
return length;
}
int zigzag(BSTNode tree, int max)
- Anonymous December 19, 2011{
int countl=0;countr=0;
//checking left zigzag
while(1)
{
if(tree.left()!=NULL)
{
tree=tree.left();
countl++;
}
else
break;
if(tree.right()!=NULL)
{
tree=tree.right();
countl++;
}
else
break;
}
if(countl>max)
max=countl;
//now check for right zizzag
while(1)
{
if(tree.right()!=NULL)
{
tree=tree.right();
countr++;
}
else
break;
if(tree.left()!=NULL)
{
tree=tree.left();
countr++;
}
else
break;
}
if(countr>max)
max=countr;
//recursively check for all nodes
max=zigzag(tree.left(),max);
max=zigzag(tree.right(),max);
return max;
}