Merge Two Binary Trees Easy 0 attempts
LeetCode ↗

Merge Two Binary Trees

Easy TreeBinary TreeDFS LeetCode

You get the roots of two binary trees. Build a merged tree as follows. Start from both roots. If both nodes exist at the same position, the merged node’s value is the sum of the two values. If only one side exists, that node is used as in that tree. Return the root of the merged tree.

You may reuse nodes from the inputs instead of building a completely separate tree, if you prefer.

Input Format
Implement mergeTrees(t1, t2). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement. Returned trees are displayed as level-order arrays, trimming trailing nulls.

Sample Input and Output

Example 1 · Run Sample

Input
t1 = [1,3,2,5]
t2 = [2,1,3,null,4,null,7]
Output
[3,4,5,5,4,null,7]

Example 2

Input
t1 = []
t2 = [1]
Output
[1]
Constraints
  • 0 <= number of nodes <= 2000
  • -10^4 <= Node.val <= 10^4
Test Cases (2)
Case 1
Args: [[1,3,2,5],[2,1,3,null,4,null,7]] Expected: [3,4,5,5,4,null,7]
Case 2
Args: [[],[1]] Expected: [1]
Topics
TreeBinary TreeDFS

Recursive DFS

javascript
function mergeTrees(t1, t2) {
  if (!t1) return t2;
  if (!t2) return t1;
  return {
    val: t1.val + t2.val,
    left: mergeTrees(t1.left, t2.left),
    right: mergeTrees(t1.right, t2.right)
  };
}

Time: O(n) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript