# 236. Lowest Common Ancestor of a Binary Tree

--

Check out the problem description here.

**Solution**

*Approach 1:*

Store both the paths to p and q , in to 2 arrays , by traversing the tree . And finally compare the array elements to see the common ancestor. The LCA will be the last common element in both array from left to right in the array.

*Time: O(N)+O(N)+O(h)+O(h)*

*Time for traversing the tree 2 times(O(N)) and comparing the 2 arrays of size h*

*Space: O(h)+O(h)+O(h)+O(h)*

*2 stack space for traversing the tree 2 times , and 2 arrays generated for paths of p and q*

*Approach 2:*

More efficient method by traversing the tree.

*Recursively traverse the tree and if the node value of it is found to be equal to p or q, then that node is returned .Also at a particular node if its left and right value is found to be p and q respectively. Then the LCA is this particular node, which is returned.*

`class Solution:`

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

return self.rec(root,p,q)

def rec(self,root,p,q):

if root ==None or (root==p) or (root==q):

return root

left =self.rec(root.left,p,q)

right = self.rec(root.right,p,q)

if left ==None:

return right

elif right ==None:

return left

else:

return root

Time: O(N)

Space: O(h) -> *height of the tree*