# 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