Subj : Re: Splitting a tree quickly
To   : comp.programming,sci.math
From : Roger Willcocks
Date : Sun Oct 09 2005 09:49 am

"Stephen White" <mildredtoede@yahoo.com> wrote in message 
news:1128796054.147969.90280@g49g2000cwa.googlegroups.com...
> Hello,
>
>      Is there a simple way to quickly split a tree (in the graph
> theoretical sense) roughly in half by removing an edge?
>      So the actual work is finding the appropriate edge.
>      Specifically, could you find an edge such that the parts of the
> tree on either side of the edge each have at most 2n/3 vertices (where
> n is the number of nodes in the original tree)?  Could this be done in
> O(n) or at least O(n log n) time?  If this is infeasible, what about if
> we tolerated at most (2n+4)/3 vertices on either side?
>
>     Thanks for any help you can offer.
>

If you have pointers to the leftmost and rightmost nodes in the tree, and do 
an intree walk with both pointers, where they cross (as they must) is where 
to snip. This is obviously O(N).

--
Roger

.