Solving LeetCode’s ‘Merge Two Binary Trees’
You are given two binary trees
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.
Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]Output: [3,4,5,5,4,null,7]
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.
Time complexity — O(n)
Space complexity — O(logn)
LeetCode Problem: https://leetcode.com/problems/merge-two-binary-trees/