wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> find diameter of binary tree.
        
(Message started by: inexorable on Jul 31^st, 2011, 6:14pm)

Title: find diameter of binary tree.
Post by inexorable on Jul 31^st, 2011, 6:14pm

The diameter of a tree is the number of nodes on the longest path between two leaves in the tree.
Find the diameter of binary tree?

Title: Re: find diameter of binary tree.
Post by Grimbal on Aug 1^st, 2011, 5:26am

recursively
[hide]diameter = max{ left branch diameter , right branch diameter , left branch max depth + right branch max depth }[/hide]

I am sure I have seen that one before.

Title: Re: find diameter of binary tree.
Post by Hippo on Sep 12^th, 2011, 1:53pm

For those interested in dynamic graph algorithms ... Thorup at all find a data structure called Top trees allowing maintanance of forests with following operations: Insert edge (joining two trees), Delete an edge (cut a tree), Find a diameter of tree containing given vertex.

Updates took O(log n) (and this (precomputed during updates) query O(1)).

(Top trees are not specialised to diameter, they are much more general ... more interesting thing connected to this problem is they could return the tree center in O(log n) as well.)

Title: Re: find diameter of binary tree.
Post by henrikk on Feb 19^th, 2012, 10:39pm

diameter (T) = max( max( diameter(T->left), diameter(T->right) ) , height(T->left) + 1 + height(T->right) );

http://www.geeksforgeeks.org/archives/5687