> For the complete documentation index, see [llms.txt](https://851958789.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://851958789.gitbook.io/notes/0236_lowest_common_ancestor_of_a_binary_tree/slt.md).

# Solution 1 DFS

* t-complexity: O(N) N is number of nodes
* s-complexity: O(N) in worst case, recursion depth is N

three cases for root is p and q's lowest common ancester:

1. p and q are in root's sub-trees, and is not in same side
2. p == root, q is in root's left or right sub-tree
3. q == root, p is in root's left or right sub-tree