# Merging Binary Trees - Amazon Top Interview Questions

### Problem Statement :

```Given two binary trees node0 and node1, return a merge of the two trees where each value is equal to the sum of the values of the corresponding nodes of the input trees. If only one input tree has a node in a given position, the corresponding node in the new tree should match that input node.

Constraints

n ≤ 100,000 where n is the number of nodes in node0
m ≤ 100,000 where m is the number of nodes in node1

Example 1

Input

node0 = [0, [3, null, null], [2, [3, null, null], null]]
node1 = [7, [5, null, null], [1, null, null]]

Output

[7, [8, null, null], [3, [3, null, null], null]]

Example 2

Input

node0 = [1, [2, [3, null, null], null], null]
node1 = [4, null, [5, null, [6, null, null]]]

Output

[5, [2, [3, null, null], null], [5, null, [6, null, null]]]```

### Solution :

```                        ```Solution in C++ :

Tree* solve(Tree* node0, Tree* node1) {
if (!node0)
return node1;
else if (!node1)
return node0;
else {
node0->val += node1->val;
auto left = solve(node0->left, node1->left);
auto right = solve(node0->right, node1->right);
node0->left = left;
node0->right = right;
return node0;
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, node0, node1):
if not node0:
return node1
if not node1:
return node0

node0.left = self.solve(node0.left, node1.left)
node0.val += node1.val
node0.right = self.solve(node0.right, node1.right)

return node0```
```

## Pair Sums

Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v

## Lazy White Falcon

White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi

## Ticket to Ride

Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n - 1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if o

## Heavy Light White Falcon

Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem. You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries: "1 u x" assign x to the value of the node . "2 u v" print the maxim

## Number Game on a Tree

Andy and Lily love playing games with numbers and trees. Today they have a tree consisting of n nodes and n -1 edges. Each edge i has an integer weight, wi. Before the game starts, Andy chooses an unordered pair of distinct nodes, ( u , v ), and uses all the edge weights present on the unique path from node u to node v to construct a list of numbers. For example, in the diagram below, Andy

## Heavy Light 2 White Falcon

White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment. You are given a tree with N nodes and each node's value Vi is initially 0. Let's denote the path fr