bfs/dfs will work but will be complex.
First do a BFS from root node, and reach a corner(leaf node). This node
will always be the part of solution, so you will do another BFS from this
leaf node. For this you need to store for every node their parent and child
pointers.
@lucifier +1
On Sun, Mar
How to find the two most distant nodes in a binary tree.
Its not about calculating the diameter of tree, but the two end nodes in
the diameter of the tree.
Optimal algorithm expected ..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To
the path we are looking for is surely between two leaf nodes.
start from the root and go to the deepest leaf node.. (dfs/bfs)
from that node traverse the entire tree to find the longest path that
exists (dfs/bfs)
u can keep track of the last node u visit in two variables for every path
and
@kartikeyan : +1
yes...bfs/dfs from the leave node will work.
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/