CODEWITHSUNDEEP
pythonalgorithmrecursionbinary-tree
Ali
Ali

Reputation: 5476

Python Weird Return Issue

I'm trying to implement a function that takes two root nodes (Binary Tree) and traverses and checks if they're identical. Here is how I got so far;

def inorder(p, q):
  if p and q:
    inorder(p.left, q.left)
    if p.val != q.val:
      return False
    inorder(p.right, q.right)
    return True

Even though when I add some printing into function I can see that p.val clearly not equal to q.val it still returns True. I couldn't figure it out. Is it returning twice because of the recursion stack calls?

Upvotes: 1

Views: 97

Answers (2)

Ante
Ante

Reputation: 5448

You have to stop if inorder() returns False, and if only one of p or q exists than return False.

def inorder(p, q):
  if p and q:
    if not inorder(p.left, q.left):
      return False
    if p.val != q.val:
      return False
    return inorder(p.right, q.right)
  return not p and not q

Upvotes: 1

Bartosz Marcinkowski
Bartosz Marcinkowski

Reputation: 6861

Your code did not check the result of inorder calls for children. If p and q had same root values, you would always return True, even if inorder(p.left, q.left) returned False. Here is corrected code:

def inorder(p, q):
    if p is None and q is None:
        return True
    elif p is not None and q is not None:
        return (
            p.val == q.val 
            and inorder(p.left, q.left)
            and inorder(p.right, q.right)
        )

Upvotes: 3

Related Questions