Lowest Common Ancestor of a Binary Tree -- LeetCode 236

[Question]
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition
[Analysis]
The simple solution is to find a pre-order path to Node A and another pre-order path to Node B. The last Node of common part of the two paths is the LCA. This solution will require extra storage to store path from root to Node A or B. The time complexity is O(N) -- because this is Binary Tree, although three traversals will be needed.

Another solution is to use recursion. The LCA is the lowest visiting node, which either has one target node in left sub tree and the other in right substree, or the visiting node is one of the target node and the other target node is in its sub trees.

A similar question is to find LCA of a Binary Search Tree (BST). Since nodes of BST are placed sequentially, the logic can be simplified using the values of the current node X,  the given Node A and Node B. One regularity that can be used is, in pre-order traversal, the first node X, whose value is between A and B's values is the LCA of A and B.

[Solution]
//
// -- LCA of Binary Tree --
//
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root==p || root==q) return root;
       
        auto left = lowestCommonAncestor(root->left, p, q);
        auto right= lowestCommonAncestor(root->right, p, q);
       
        return !left ? right : right ? root : left;
    }

//
//-- LCA of Binary Search Tree --
//
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root==NULL|| root==p || root==q) return root;
        if (min(p->val,q->val) < root->val && root->val < max( p->val,q->val) )
             return root;
     
        return root->val > p->val ? lowestCommonAncestor(root->left, p, q): lowestCommonAncestor(root->right, p, q);
 
    }
};