CODEWITHSUNDEEP
algorithmrecursiondata-structuresbinary-tree
stillearning
stillearning

Reputation: 403

Merging two binary trees node sum

I was working on the problem of merging two binary trees node sum (https://www.geeksforgeeks.org/merge-two-binary-trees-node-sum/) and I was having trouble understanding some of the recursion. Why would you set the recursion statements to t1.left and t1.right? When you do this does t1.left equal two values?

I'm just not sure why we would set the recursion statements to t1.leftort1.right`

class newNode: 
def __init__(self, data): 
    self.data = data  
    self.left = self.right = None


def inorder(node): 
    if (not node): 
        return

inorder(node.left)  

print(node.data, end = " ")  

inorder(node.right) 


def MergeTrees(t1, t2): 
    if (not t1):  
        return t2  
    if (not t2): 
        return t1  
    t1.data += t2.data  
    t1.left = MergeTrees(t1.left, t2.left)  
    t1.right = MergeTrees(t1.right, t2.right)  
    return t1 

if __name__ == '__main__': 

# Let us construct the first Binary Tree  
#    1  
#    / \  
#    2   3  
# / \    \  
# 4 5    6  
root1 = newNode(1)  
root1.left = newNode(2)  
root1.right = newNode(3)  
root1.left.left = newNode(4)  
root1.left.right = newNode(5)  
root1.right.right = newNode(6)  

# Let us construct the second Binary Tree  
#    4  
#    / \  
# 1  7  
# /  / \  
# 3  2 6  
root2 = newNode(4)  
root2.left = newNode(1)  
root2.right = newNode(7)  
root2.left.left = newNode(3)  
root2.right.left = newNode(2)  
root2.right.right = newNode(6)  

root3 = MergeTrees(root1, root2)  
print("The Merged Binary Tree is:")  
inorder(root3)

Upvotes: 0

Views: 117

Answers (2)

Mulan
Mulan

Reputation: 135416

First make it possible to set the left and right branches when you are constructing a Node -

class Node:
  def __init__(self, data, left = None, right = None):
    self.data = data
    self.left = left
    self.right = right

Now instead of mutating trees using node.left = ... and node.right = ..., we can construct them directly -

# Let us construct the first Binary Tree  
#     1  
#    / \  
#   2   3  
#  / \   \  
# 4   5   6  

t1 = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))

Before we go on, let's implement __str__ on Node so we can visualise the trees -

class Node:
  def __init__(...):
    # ...

  def __str__(self, pre="", child=""):
    if self is None:
      return "()"
    else:
      return f"({self.data} {self.left} {self.right})"

print(t1)
# (1 (2 (4 None None) (5 None None)) (3 None (6 None None)))

Now let's implement merge. Having the ability to specify the left and right values in the Node constructor makes it easier to write this -

def merge(t1, t2):
  if t1 is None and t2 is None:
    return None
  elif t1 is None:
    return t2
  elif t2 is None:
    return t1
  else:
    return Node(t1.data + t2.data, merge(t1.left, t2.left), merge(t1.right, t2.right)

print(merge(t1, t1))
# (2 (4 (8 None None) (10 None None)) (6 None (12 None None)))

Now we can see how + could easily some other operation. Adding another parameter to merge makes it possible to merge using any operation -

def merge(f, t1, t2):
  if t1 is None and t2 is None:
    return None
  elif t1 is None:
    return t2
  elif t2 is None:
    return t1
  else:
    return Node(
      f(t1.data, t2.data),
      merge(f, t1.left, t2.left),
      merge(f, t1.right, t2.right)
    )

print(merge(lambda a, b: a + b, t1, t1))
# (2 (4 (8 None None) (10 None None)) (6 None (12 None None)))

print(merge(lambda a, b: a * b, t1, t1))
# (1 (4 (16 None None) (25 None None)) (9 None (36 None None)))

Or using operator module -

from operator import add, mul

print(merge(add, t1, t1))
# (2 (4 (8 None None) (10 None None)) (6 None (12 None None)))

print(merge(mul, t1, t1))
# (1 (4 (16 None None) (25 None None)) (9 None (36 None None)))

Upvotes: 1

Prune
Prune

Reputation: 77900

To merge the trees using recursion, you follow the typical formula:

  1. Operate on the current node
  2. Operate on one child
  3. Operate on the other child

In this case, it's quite convenient the the merge can be done in-place for one of the trees. You merge the current root node. Then you recur on the left child, which merges t2.left into t1.left; you assign this to t1.left so that the merged left subtree cleanly replaces the original. You do the same for the right subtree.

Is it clear yet?

Upvotes: 1

Related Questions