236. Lowest Common Ancestor of a Binary Tree
Check out the problem description here.
Lowest Common Ancestor of a Binary Tree - LeetCode
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition…
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 for traversing the tree 2 times(O(N)) and comparing the 2 arrays of size h
2 stack space for traversing the tree 2 times , and 2 arrays generated for paths of p and q
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.
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root ==None or (root==p) or (root==q):
right = self.rec(root.right,p,q)
if left ==None:
elif right ==None:
Space: O(h) -> height of the tree