Tree traversal

[ahgu00321]

Hi everyone,

I have a question on tree traversal, if I want to find the lowest common ancestor, what kind of traversal can I use? I was thinking of Euler Tour, but does that traversal only restricted to binary tree? because my question does not mention that it is a binary tree.

[Rashakil Fol]

It depends on how your tree is structured. Do leaf nodes contain pointers to their parents? Or is it that parents contain pointers to their children, and that you're only given the root node and the addresses of the two particular leaf nodes? In the former case, you can do this in O(h) time with constant memory usage.