Chandler Hanson

Jun 27, 2021

2 min read

Solving LeetCode’s ‘Merge Two Binary Trees’

Photo by Ralph (Ravi) Kayden on Unsplash

In this article, we will be solving LeetCode’s ‘Merge Two Binary Trees’ in JavaScript. This problem uses the binary search tree data structure. For a quick definition of a binary search tree (BST), a BST is a data structure in which each node has at most two children. The value of each left node is less than its parent, while the value of each right node is greater than its parent. I linked my article on BST that goes into more detail at the bottom.

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.

Example

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

Solution

Explanation

We start at the root node of both trees and traverse them in a preorder fashion. I took a recursive approach to solve this problem. A recursive function is a function that calls on itself until the function reaches its base case. The base case is the end condition where we do not need to call on the function anymore.

We check to see if one of the given trees are null, we return the other node. If the nodes in both the trees are not null, we update the first tree’s node value with the sum of the two values. We call the same method to recursively traverse through the left and right paths of both trees. Once the recursion end, we can finally return the updated tree.

Big O

Time complexity — O(n)

Space complexity — O(logn)

Resources

LeetCode Problem: https://leetcode.com/problems/merge-two-binary-trees/

My BST article: https://chandler-hanson.medium.com/the-basics-of-binary-search-trees-f11ac89b87cf

My recursion article: https://medium.com/analytics-vidhya/recursion-the-nesting-doll-of-programming-404ae61708a0

BST demo: https://www.cs.usfca.edu/~galles/visualization/BST.html

https://www.geeksforgeeks.org/merge-two-binary-trees-node-sum/

https://medium.com/@ramyjzh/data-structures-for-dummies-binary-search-trees-13f87a1313a2

https://medium.com/swlh/understanding-data-structures-binary-search-trees-a6612daf00dd