Directi Interview Question
Software Engineer / Developersfor binary tree :
1> find two longest path from root to leaf
2>the center of these two path( go in to the longest path by a distance of the difference of these two path) is the center of the complete tree
and these two( the longest paths) together make the diameter of the tree.
It is NOT AT ALL NECESSARY that root falls on the longest path. Try making a tree with 2 longest paths from one of the child nodes. It'd fail.
The whole idea is to find the diameter of the tree, which is the longest path between any two leaf nodes and find the mid point of it.
In graph theory, a tree is defined as a graph on N nodes,and (N-1)
un-directed edges such that there are no cycles in the graph.Each node
has a single unique path to every other node.
Let D(u,v) be the number of edges in the unique path from node 'u' to
node 'v' (or from node 'v' to 'u' since the edges are
un-directed).D(u,u) is 0 for all nodes 'u'.
M(u)=MAX(D(u,i):for all nodes i)
The center of a tree is the node (or nodes) 'u',for which M(u) is
minimum among all the nodes in the graph.
You'll be given a graph which has N nodes (1<=N<=20).The nodes are
labeled 1,2,3,..N.You will be provided with N-1 edges in the form of
"a b" pairs where 1<=a,b<=N.No edge will be repeated.You can assume
that the edges are specified such that the graph is a valid tree as
defined above.
Output the node labels of the center(or centers) of the tree.
Sample Input:
6(value of N)
1 3 (edges)
1 4
1 2
2 5
2 6
Sample Output
1
2
Expected:O(N) complexity algo
can anyone plz help me out with O(N) algo?
What exactly does the "center of a tree" mean?
- Anon October 05, 2010