Solving LeetCode’s ‘Merge Two Binary Trees’

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

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

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/

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