CODEWITHSUNDEEP
binary-treeleast-common-ancestor
user14955967
user14955967

Reputation:

How does "if right and left: return root" and the "return right or left" help us find the least common ancestor?

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def insert(temp,data):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         if data is not None:
            temp.left = TreeNode(data)
         else:
            temp.left = TreeNode(0)
         break
      else:
         que.append(temp.left)
         if (not temp.right):
            if data is not None:
               temp.right = TreeNode(data)
            else:
               temp.right = TreeNode(0)
            break
         else:
            que.append(temp.right)
def make_tree(elements):
   Tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
   return Tree
class Solution(object):
   def lowestCommonAncestor(self, root, p, q):
      if not root:
         return None
      if root.data == p or root.data ==q:
         return root
      left = self.lowestCommonAncestor(root.left, p, q)
      right = self.lowestCommonAncestor(root.right, p, q)
      **if right and left:
         return root**
      *return right or left*
ob1 = Solution()

tree = make_tree([3,5,1,6,2,0,8,None,None,7,4])
print(ob1.lowestCommonAncestor(tree, 5, 1).data)

Why do we return right or left when we want to return a single node rather than two?

I realized that the boolean "right and left" returns true even if right and left are not the same TreeNode. Also, there's no comparison function written. Is that necessary?

Upvotes: 0

Views: 573

Answers (1)

Yuri Ginsburg
Yuri Ginsburg

Reputation: 2601

return right or left returns right if it is not None, otherwise, it checks left and returns left, if it's not None. If both left and right are None returns None. So, only one node or None is returned.

if right and left is True only if both left and right are not None

Upvotes: 0

Related Questions