Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Merge Two Binary Trees solution and explanation

EasyBinary TreeBreadth-First SearchDepth-First SearchTree5 min read79.2% acceptanceUpdated 9 Apr 2026
Asked atLinkedInJosh TechnologyMongoDBAmazonMetaGoogle
+2 moreMicrosoftBloomberg
Practise Merge Two Binary Trees
11:57
Merge Two Binary Trees - Leetcode 617NeetCode · 11:57 · 70K viewsWatch on YouTube
9 more videos on this problem
  1. Merge Two Binary Trees - Leetcode 617NeetCode · 11:57 · 70K views
  2. LeetCode Merge Two Binary Trees Solution Explained - JavaNick White · 7:28 · 52K views
  3. Leetcode #617 - Merge Two Binary Trees (Solution)Algorithms Illustrator · 8:16 · 10K views
  4. LeetCode 617. Merge Two Binary Trees [Solution + Code Explained ]jayati tiwari · 6:51 · 8K views
  5. Merge Two Binary Trees | Live Coding with Explanation | Leetcode - 617Algorithms Made Easy · 25:53 · 6K views
  6. Facebook Coding Interview Question - Merge Two Binary TreesPotato Coders · 7:09 · 3K views
  7. 617. Merge Two Binary Trees Java SolutionCode with Carter · 4:34 · 622 views
  8. (Old) Leetcode 617 - Merge Binary Tree | Binary TreeNideesh Terapalli · 2:39 · 598 views
  9. 617. Merge Two Binary Trees (Leetcode Easy)Programming Live with Larry · 5:34 · 345 views
  10. Leetcode | 617 Merge Two Binary Trees | Python3 | Recursion + Binary Tree | Explanationygongcode · 12:49 · 345 views

The problem

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

Example 1:

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

Example 2:

Input: root1 = [1], root2 = [1,2]
Output: [2,2]

Constraints:

  • The number of nodes in both trees is in the range [0, 2000].
  • -104 <= Node.val <= 104

Approach overview

Problem Overview: You receive two binary trees. If two nodes overlap, their values are summed. If only one node exists at a position, that node becomes part of the merged tree. The goal is to return the root of the merged tree.

Approach 1: Recursive Depth-First Search (O(n) time, O(h) space)

This approach uses recursion to traverse both trees simultaneously. For each pair of nodes, add their values and recursively merge their left and right children. If one node is null, return the other node directly. The recursion naturally follows the structure of the trees, making the implementation concise and easy to reason about. Time complexity is O(n) where n is the total number of nodes across both trees, because each node is processed once. Space complexity is O(h) from the recursion stack, where h is the height of the tree.

This approach directly leverages Depth-First Search traversal on a Binary Tree. It modifies or builds nodes as the recursion unwinds.

Approach 2: Iterative Traversal with Queue or Stack (O(n) time, O(n) space)

An iterative strategy avoids recursion by explicitly managing traversal with a queue (BFS) or stack (DFS). Start with the pair of root nodes. While the data structure is not empty, pop a node pair and merge their values. For children, if both nodes exist, push the pair for later processing. If a child exists in only one tree, attach it directly to the merged tree. This simulates the recursive traversal but uses an explicit structure to track work.

The algorithm still processes each node once, giving O(n) time complexity. Space complexity becomes O(n) in the worst case due to the queue or stack holding node pairs. Using a queue corresponds to Breadth-First Search, which processes the tree level by level.

Recommended for interviews: The recursive DFS solution is the expected answer. It clearly shows understanding of binary tree traversal and keeps the code minimal. Interviewers often look for the base-case handling (null nodes) and correct recursive merging of children. The iterative version demonstrates deeper control over traversal mechanics and is useful when recursion depth might be a concern.

Approach 1: Recursive Approach

This approach utilizes recursion to traverse both trees simultaneously. If both node values are non-null, we sum them up as the new value and recursively merge their left and right children. If one node is null, we return the non-null node.

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def mergeTrees(t1, t2):
    if not t1:
        return t2
    if not t2:
        return t1
    t1.val += t2.val
    t1.left = mergeTrees(t1.left, t2.left)
    t1.right = mergeTrees(t1.right, t2.right)
    return t1
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        t1.val += t2.val;
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }
}
#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    if (!root1) return root2;
    if (!root2) return root1;
    root1->val += root2->val;
    root1->left = mergeTrees(root1->left, root2->left);
    root1->right = mergeTrees(root1->right, root2->right);
    return root1;
}
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var mergeTrees = function(t1, t2) {
    if (!t1) return t2;
    if (!t2) return t1;
    t1.val += t2.val;
    t1.left = mergeTrees(t1.left, t2.left);
    t1.right = mergeTrees(t1.right, t2.right);
    return t1;
};
#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2) {
    if (!root1) return root2;
    if (!root2) return root1;
    root1->val += root2->val;
    root1->left = mergeTrees(root1->left, root2->left);
    root1->right = mergeTrees(root1->right, root2->right);
    return root1;
}
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode MergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        t1.val += t2.val;
        t1.left = MergeTrees(t1.left, t2.left);
        t1.right = MergeTrees(t1.right, t2.right);
        return t1;
    }
}

This Python solution uses recursion to merge two binary trees. If either node is None, the function returns the other. Otherwise, it sums node values and recursively merges the child nodes.

Complexity

Time Complexity: O(n); Space Complexity: O(h), where n is the total number of nodes and h is the height of the tree.

Try this approach in the editor

Approach 2: Iterative Approach

This approach uses an iterative method with a stack to simulate the recursive calls for merging the two binary trees. We traverse the trees using a stack and merge nodes at each level iteratively.

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def mergeTrees(t1, t2):
    if not t1:
        return t2
    if not t2:
        return t1
    stack = [(t1, t2)]
    while stack:
        n1, n2 = stack.pop()
        if not n1 or not n2:
            continue
        n1.val += n2.val
        if not n1.left:
            n1.left = n2.left
        else:
            stack.append((n1.left, n2.left))
        if not n1.right:
            n1.right = n2.right
        else:
            stack.append((n1.right, n2.right))
    return t1
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        Stack<TreeNode[]> stack = new Stack<>();
        stack.push(new TreeNode[] { t1, t2 });
        while (!stack.isEmpty()) {
            TreeNode[] t = stack.pop();
            if (t[0] == null || t[1] == null) continue;
            t[0].val += t[1].val;
            if (t[0].left == null) {
                t[0].left = t[1].left;
            } else {
                stack.push(new TreeNode[] { t[0].left, t[1].left });
            }
            if (t[0].right == null) {
                t[0].right = t[1].right;
            } else {
                stack.push(new TreeNode[] { t[0].right, t[1].right });
            }
        }
        return t1;
    }
}
#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    if (!root1) return root2;
    if (!root2) return root1;
    stack<pair<TreeNode*, TreeNode*>> stk;
    stk.push({root1, root2});
    while (!stk.empty()) {
        auto [n1, n2] = stk.top();
        stk.pop();
        if (!n1 || !n2) continue;
        n1->val += n2->val;
        if (!n1->left) {
            n1->left = n2->left;
        } else {
            stk.push({n1->left, n2->left});
        }
        if (!n1->right) {
            n1->right = n2->right;
        } else {
            stk.push({n1->right, n2->right});
        }
    }
    return root1;
}
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var mergeTrees = function(t1, t2) {
    if (!t1) return t2;
    if (!t2) return t1;
    let stack = [[t1, t2]];
    while (stack.length > 0) {
        let [n1, n2] = stack.pop();
        if (!n1 || !n2) continue;
        n1.val += n2.val;
        if (!n1.left) {
            n1.left = n2.left;
        } else {
            stack.push([n1.left, n2.left]);
        }
        if (!n1.right) {
            n1.right = n2.right;
        } else {
            stack.push([n1.right, n2.right]);
        }
    }
    return t1;
};
#include <stdio.h>
#include <stdlib.h>
#include <stack>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2) {
    if (!root1) return root2;
    if (!root2) return root1;
    std::stack<std::pair<TreeNode*, TreeNode*>> stack;
    stack.push({root1, root2});
    while (!stack.empty()) {
        auto p = stack.top();
        stack.pop();
        if (!p.first || !p.second) continue;
        p.first->val += p.second->val;
        if (!p.first->left) {
            p.first->left = p.second->left;
        } else {
            stack.push({p.first->left, p.second->left});
        }
        if (!p.first->right) {
            p.first->right = p.second->right;
        } else {
            stack.push({p.first->right, p.second->right});
        }
    }
    return root1;
}
using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode MergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        Stack<TreeNode[]> stack = new Stack<TreeNode[]>();
        stack.Push(new TreeNode[] { t1, t2 });
        while (stack.Count > 0) {
            TreeNode[] t = stack.Pop();
            if (t[0] == null || t[1] == null) continue;
            t[0].val += t[1].val;
            if (t[0].left == null) {
                t[0].left = t[1].left;
            } else {
                stack.Push(new TreeNode[] { t[0].left, t[1].left });
            }
            if (t[0].right == null) {
                t[0].right = t[1].right;
            } else {
                stack.Push(new TreeNode[] { t[0].right, t[1].right });
            }
        }
        return t1;
    }
}

This Python solution uses a stack for an iterative merge. By pairing nodes, we handle the overlap and non-overlap cases explicitly by managing a stack to traverse and combine nodes iteratively.

Complexity

Time Complexity: O(n); Space Complexity: O(h), where n is the number of nodes and h represents the max height of the trees.

Try this approach in the editor

Approach 3: Default Approach

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function mergeTrees(root1: TreeNode | null, root2: TreeNode | null): TreeNode | null {
    if (root1 === null && root2 === null) return null;
    if (root1 === null) return root2;
    if (root2 === null) return root1;
    const left = mergeTrees(root1.left, root2.left);
    const right = mergeTrees(root1.right, root2.right);
    return new TreeNode(root1.val + root2.val, left, right);
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
	if root1 == nil {
		return root2
	}
	if root2 == nil {
		return root1
	}
	node := &TreeNode{Val: root1.Val + root2.Val}
	node.Left = mergeTrees(root1.Left, root2.Left)
	node.Right = mergeTrees(root1.Right, root2.Right)
	return node
}
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn merge_trees(
        root1: Option<Rc<RefCell<TreeNode>>>,
        root2: Option<Rc<RefCell<TreeNode>>>,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        match (root1.is_some(), root2.is_some()) {
            (false, false) => None,
            (true, false) => root1,
            (false, true) => root2,
            (true, true) => {
                {
                    let mut r1 = root1.as_ref().unwrap().borrow_mut();
                    let mut r2 = root2.as_ref().unwrap().borrow_mut();
                    r1.val += r2.val;
                    r1.left = Self::merge_trees(r1.left.take(), r2.left.take());
                    r1.right = Self::merge_trees(r1.right.take(), r2.right.take());
                }
                root1
            }
        }
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Recursive Approach

Time Complexity: O(n); Space Complexity: O(h), where n is the total number of nodes and h is the height of the tree.

Iterative Approach

Time Complexity: O(n); Space Complexity: O(h), where n is the number of nodes and h represents the max height of the trees.

Default Approach–

Complexity analysis

ApproachTimeSpaceWhen to Use
Recursive Depth-First SearchO(n)O(h)Best general solution. Clean code and natural fit for binary tree recursion.
Iterative Traversal (Queue/Stack)O(n)O(n)Useful when avoiding recursion or when recursion depth may cause stack overflow.

Frequently asked questions

Is Merge Two Binary Trees easy or hard?

Merge Two Binary Trees is classified as an Easy problem on LeetCode. It mainly tests understanding of binary tree traversal and handling null nodes during recursion or iteration.

Merge Two Binary Trees Python/Java solution

Python and Java implementations usually follow the recursive DFS pattern. The function checks for null nodes, sums the values of overlapping nodes, and recursively merges the left and right children before returning the merged root.

How to solve Merge Two Binary Trees in O(n)?

Traverse both trees simultaneously using DFS or BFS. When two nodes overlap, sum their values and continue merging their children. If one node is null, return the other node directly. Since every node is processed once, the algorithm runs in O(n) time.

What is the best approach for Merge Two Binary Trees?

The recursive depth-first search approach is the most common solution. Traverse both trees simultaneously, sum overlapping nodes, and recursively merge their children. This method processes each node once and runs in O(n) time with O(h) recursion stack space.

Is Merge Two Binary Trees asked at Google/Amazon/Meta?

Binary tree traversal and merging problems appear frequently in interviews at companies like Amazon and Meta. While this exact problem may vary in wording, the core concept—simultaneous traversal of two trees—is commonly tested.

What data structure is used in Merge Two Binary Trees?

The problem uses the binary tree data structure. The solution typically applies depth-first search with recursion or breadth-first search using a queue to traverse and merge nodes.

What is the time complexity of Merge Two Binary Trees?

The time complexity is O(n), where n is the total number of nodes across both trees. Each node is visited once during the traversal. Space complexity is O(h) for recursion depth in the DFS approach or O(n) when using an iterative queue or stack.

Comments

Now write it yourselfClose this page and solve Merge Two Binary Trees in the editor, without looking.
Practise Merge Two Binary Trees