you will have to take top-down/bottom-up approach.
getMaxWidth(node tree){
int n = getHeight(tree), w=1;
for(int i=1; i< n; i++){
w = getWidth(tree, i);
if(w <= maxWidth)
continue;
else
maxWidth = w;
}
Syso("Maximum width is"+maxWidth);
}
getWidth(node tree,level l){
do a bfs traversal and insert a null marker after each traversal keep a
variable max for maximum nodes at any level..
O(n)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To un
@anand:diameter is 4 bhaiya its the widththe shortest distance between
the leftmost nodein left subtree and right most node in right subtree
On Sat, Jun 19, 2010 at 8:07 AM, Anand wrote:
> Here is the example tree.
>
> 1
> / \
>23
> / \ \
> 4
Here is the example tree.
1
/ \
23
/ \ \
45 8
/ \
67
For the above tree,
width of level 1 is 1,
width of level 2 is 2,
width of level 3 is 3
width of level 4 is 2.
So the maximum width of the tree is 3.
On Thu,
do u meand diameter of tree?? if it is so then start from the left most node
in tree and traverse upto root and traverse to the rightmost node in
tree..this u can do by having extra field in tree which is parent
pointer
On Fri, Jun 18, 2010 at 4:25 AM, Anand wrote:
> Any guys suggest any alg
Any guys suggest any algo on how to find the width of the tree.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr