Lowest Common Ancestor

There are many ways to solve the LCA problem.

1. Binary Lifting, $O(N\log N)$ preprocessing, $O(\log N)$ for each query
2. Sparse Table, $O(N\log N)$ preprocessing, $O(1)$ for each query

For regular LeetCode, one of the ways you can approach is doing it recursively.

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
	if (root == nullptr) {
		return nullptr;
	}
	if (root == p || root == q) {
		return root;
		
	}
	TreeNode* l = lowestCommonAncestor(root->left, p,q);
	TreeNode* r = lowestCommonAncestor(root->right, p,q);
	
		
	if (l && r) {
		return root;
	} else if (l){
		return l;
	} else if (r) {
		return r;
	} else {
		return nullptr;
	}