This is a sample solution given to the premium subscribers of my newsletter. Being a premium subscriber gives you access to a library of high-class solutions, and one on one time with me to help with your interview preparation. To join others acing their software development interviews subscribe here:
Problem
This problem was asked by Salesforce.
Write a program to merge two binary trees. Each node in the new tree should hold a value equal to the sum of the values of the corresponding nodes of the input trees.
If only one input tree has a node in a given position, the corresponding node in the new tree should match that input node.
Step 1: Find the base cases
Most tree problems can be framed recursively. This is because a tree is defined as
def TreeNode(Value val, TreeNode left, TreeNode right)
Next time someone asks you why a tree is a recursive data structure, remember this.
For recursive problems, you want to find the base cases first. This has the follwing benefits:
Instead of sitting there in silence you are doing something. Much better look for an interview.
You show the interviewer that instead of just winging it, you break your problem down in an organized way.
Base cases can help orient your mind in coming up with a solution.
What base cases can we create here? Trees generally have a standard base case: What is the root is null? In our case, this would be both roots being null. Here we just return null.
What if only one is null? We can just return the other node.
This leaves with the situation where both roots are not null. Then we just have to merge them. See why that becomes the recursive case?
Step 2: Putting our recursive case together
What does merging look like? Our new root becomes the sum of the two input roots. The left sums the left, the right sums the right. Remember our base cases handle the case where any of the inputs are null, so we are guaranteed that the input root values are not null.
What does this mean? Simply put we can merge our tree doing the following:
node = Node(t1.data + t2.data)
node.left = merge(t1.left, t2.left)
node.right = merge(t1.right, t2.right)
return node
Step 3: Combining Everything
Combining everything we get the following code:
def merge(t1, t2):
if not t1 and not t2:
return None
elif not t1:
return t2
elif not t2:
return t1
else:
node = Node(t1.data + t2.data)
node.left = merge(t1.left, t2.left)
node.right = merge(t1.right, t2.right)
return node
The time complexity for this is O(m+n) where m and n are the numbers of nodes in tree 1 and 2 respectively. Since recursion uses stack frames this will also have non-constant space? What do you think the space complexity for this algorithm is? The best explanation gets a free month of premium subscription.
Step 4: Alternatives
There is another way to do this code in identical time and space using stacks. Try to work that out on your own. Message me if you want the code for that.
You can leave your solutions here:
Closing +Note about the Difficulty Level
This is an easy question. I chose to include it in the newsletter because the way to work up to the solution is very beneficial in a whole bunch of recursive/dynamic programming contexts. Make sure you study the question/how we built up very well. It will be very important.
Overall you should be able to solve this question in 20 minutes at most. Since most interviews are 45 minutes, this gives you time for follow-up questions/discussions. With easy questions, this is extremely important.
If you learnt from this, make sure to like the post and leave your comments. It really helps my channel grow
Bonuses/Promotion (Get Free Stuff)
To get access to the solution for this problem (and high-quality breakdowns of many other problems), subscribe to the publication right here. Join various other coders nailing interviews at top-tier firms such as Facebook, Microsoft, Google, Fidelity, and more:
To share interesting problems/solutions with me, reach out to me. Different social media of mine also have other content from me. Good problems and/or solutions receive a free shoutout + 2 months of the paid newsletter:
Reach out to me on Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/