236. Lowest Common Ancestor of a Binary Tree

Dhanaraj S
1 min readApr 16, 2022

--

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

--

--

Dhanaraj S
Dhanaraj S

Written by Dhanaraj S

Tech-Enthusiast, Coder,Explorer,Geeky,Software Engineer |A piece of code delivers everything that you need. The world is all about codes.