### Euler Traversal

- 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 `c`

.

Thus Euler walk/ traversal of a tree will always have the LCA for any two nodes.

### References

Written with StackEdit.

Advertisements