wu :: forums « wu :: forums - find diameter of binary tree. » Welcome, Guest. Please Login or Register. Apr 29th, 2024, 7:31am

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    cs (Moderators: Eigenray, Grimbal, Icarus, ThudnBlunder, towr, SMQ, william wu)    find diameter of binary tree. « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: find diameter of binary tree.  (Read 3504 times) inexorable Full Member     Posts: 211 find diameter of binary tree.   « on: Jul 31st, 2011, 6:14pm » Quote Modify 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?   IP Logged Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: find diameter of binary tree.   « Reply #1 on: Aug 1st, 2011, 5:26am » Quote Modify recursively diameter = max{ left branch diameter , right branch diameter , left branch max depth + right branch max depth }   I am sure I have seen that one before. IP Logged Hippo Uberpuzzler     Gender: Posts: 919 Re: find diameter of binary tree.   « Reply #2 on: Sep 12th, 2011, 1:53pm » Quote Modify 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.) « Last Edit: Sep 12th, 2011, 1:54pm by Hippo » IP Logged henrikk Newbie     Posts: 2 Re: find diameter of binary tree.   « Reply #3 on: Feb 19th, 2012, 10:39pm » Quote Modify diameter (T) = max( max( diameter(T->left), diameter(T->right) ) , height(T->left) + 1 + height(T->right) );   http://www.geeksforgeeks.org/archives/5687 IP Logged Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board