236. Lowest Common Ancestor of a Binary Tree

Check out the problem description here.

Lowest Common Ancestor of a Binary Tree - LeetCode

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