ProAnswers.org

How to find a path between two nodes in a binary tree

How to find a path between two nodes in a binary tree

You need to find the lowest common ancestor of the two nodes. Then the path will be
one node -> lowest common ancestor -> other node.
In order to find the lowest common ancestor, you can use the following algorithm:
Take one node.
Color it.
repeat until you reach the root
{
Go to its parent
Color it.
}
end
Take other node.
repeat until you get a colored node
{
Explore its parent.
}
end
The first colored node you get is the lowest common ancestor.