- Start as
ROOT --> Subtree-1 --> ROOT --> Subtree-2 --> ROOT --> Subtree-3 --> ROOT
- Recurse at each subtree as above
- All nodes of a subtree appear together, contiguously in the traversal.
Why Euler Traversal Gets LCA?
Assume we want LCA of a node
u in subtree
a and node
v in subtree
c. A Euler walk of the tree will have all nodes of the subtree
a followed by the LCA node
ROOT and all the nodes of subtree
Thus Euler walk/ traversal of a tree will always have the LCA for any two nodes.
Written with StackEdit.