While constructing the tree store it's parent+info at parent.
For example:
1(null)
2(1) 3(1)
4(2,1) 5(2,1) 6(3,1) 7(3,1)
8(4,2,1)......... and so on.
So all you have to do is search for the node which can be done in O(n)
time { where n = number of elements in the tree} and print the value
at that node.
(I've done it in reverse, but you get the idea). I doubt you can do it
in lesser than O(n) time as search in a simple binary tree is an O(n)
operation.
On Sep 6, 11:08 pm, Debajyoti Sarma <[email protected]> wrote:
> How to print the path from root to a specific node in a binary tree??
> I want to store the path in a array[] of node*.
> can it b done in O(n) or less?
> Remember it's not BST.
>
> 1
> / \
> 2 3
> / \ / \
> 4 5 6 7
> / \ / \ / \ / \
> 8 9 10 11 12 13 14 15
>
> path of 6 will b 1,3,6.
> path of 9 will be 1,2,5,11
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
