No results found for the specified position. Can you merge binary trees? Python Intermediate Level Tree Mock Interview

MockQuestions

Python Intermediate Level Tree Mock Interview

Question 2 of 8 for our Python Intermediate Level Tree Mock Interview

Get More Information About Our Python Intermediate Level Tree Interview Questions

Question 2 of 8

Can you merge binary trees?

This interview question concentrates on using Python functions.

You are given root nodes root1 and root2 of two binary trees. Your task is to merge them to form a new binary tree. The merge rules are as follows-
if both the trees have nodes at a specific position, the merged tree will have a node with a value equal to the sum of those two nodes at that position.
root1- 1 root2- 4
/ \ / \
2 3 5 6

merged- 5
/ \
7 9
At position “root”- both trees have nodes. So node in the merged tree has value 1 + 4 = 5
At position “left of the root”- both trees have nodes. So node in the merged tree has value 2 + 5 = 7
At position “right of the root”- both trees have nodes. So node in the merged tree has value 3 + 6 = 9

if one tree has null and the other tree has a node at a specific position. the merged tree will have a node with a value equal to the value of the node of the other tree.
root1- 1 root2- 4
/ \
2 6

merged- 5
/ \
2 6

At position “left of the root”- root1 has a node with value 2 but root2 doesn’t have a node. The merged tree has 2 at that position.
At position “right of the root”- root2 has a node with value 6 but root1 doesn’t have a node. The merged tree has 6 at that position.

if both the trees have null at a specific position, then the merged tree too will have null at that position.
NOTE- You need to create a new tree. You can not modify the original trees.

/*Example*/

      root1-	  1			root2-	2 
          		/   \				    /  \
  		     3    2			   1    3
		    /					    \	   \
   5						4   7

      merged-	  3
          		/   \
  		     4     5
		    / \     \
		   5   4     7

Solution:

We will use a recursive approach for this.
if both the nodes are null, we return null;
if one of them is null, we create newRoot with the value of the non-null node. Then we merge the left and right subtrees recursively;
if none of them is null, we create newRoot with a value equal to the sum of both nodes and then merge the left and right subtrees recursively.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def mergeTrees(root1, root2):
	if not root1 and not root2:
		return None
 
	if not root1:
		return root2
	if not root2:
		return root1
 
	root = TreeNode(root1.val + root2.val)
	root.left = mergeTrees(root1.left, root2.left)
	root.right = mergeTrees(root1.right, root2.right)
	return root

Time complexity- O(max(number of nodes in both trees))
Space complexity- O(max(height of both trees))

Written by on June 27th, 2021

Next Question

How to Answer: Can you merge binary trees?

Advice and answer examples written specifically for a Python Intermediate Level Tree job interview.

  • 2. Can you merge binary trees?

      This interview question concentrates on using Python functions.

      You are given root nodes root1 and root2 of two binary trees. Your task is to merge them to form a new binary tree. The merge rules are as follows-
      if both the trees have nodes at a specific position, the merged tree will have a node with a value equal to the sum of those two nodes at that position.
      root1- 1 root2- 4
      / \ / \
      2 3 5 6

      merged- 5
      / \
      7 9
      At position “root”- both trees have nodes. So node in the merged tree has value 1 + 4 = 5
      At position “left of the root”- both trees have nodes. So node in the merged tree has value 2 + 5 = 7
      At position “right of the root”- both trees have nodes. So node in the merged tree has value 3 + 6 = 9

      if one tree has null and the other tree has a node at a specific position. the merged tree will have a node with a value equal to the value of the node of the other tree.
      root1- 1 root2- 4
      / \
      2 6

      merged- 5
      / \
      2 6

      At position “left of the root”- root1 has a node with value 2 but root2 doesn’t have a node. The merged tree has 2 at that position.
      At position “right of the root”- root2 has a node with value 6 but root1 doesn’t have a node. The merged tree has 6 at that position.

      if both the trees have null at a specific position, then the merged tree too will have null at that position.
      NOTE- You need to create a new tree. You can not modify the original trees.

      /*Example*/

      root1-	  1			root2-	2 
          		/   \				    /  \
  		     3    2			   1    3
		    /					    \	   \
   5						4   7

      merged-	  3
          		/   \
  		     4     5
		    / \     \
		   5   4     7

      Solution:

      We will use a recursive approach for this.
      if both the nodes are null, we return null;
      if one of them is null, we create newRoot with the value of the non-null node. Then we merge the left and right subtrees recursively;
      if none of them is null, we create newRoot with a value equal to the sum of both nodes and then merge the left and right subtrees recursively.

      class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def mergeTrees(root1, root2):
	if not root1 and not root2:
		return None
 
	if not root1:
		return root2
	if not root2:
		return root1
 
	root = TreeNode(root1.val + root2.val)
	root.left = mergeTrees(root1.left, root2.left)
	root.right = mergeTrees(root1.right, root2.right)
	return root

      Time complexity- O(max(number of nodes in both trees))
      Space complexity- O(max(height of both trees))

      Written by S. Kumar on June 27th, 2021

    • Next Question