Merge Two Binary Trees - Leetcode 617

[@NeetCode]

Tree Question Playlist: th-cam.com/video/OnSn2XEQ4MY/w-d-xo.html

[@jugsma6676]

This would be my solution:
def merge_tree(t1, t2):
if t1 == None:
return t2
if t2 == None:
return t1
t1.val += t2.val
t1.left = merge_tree(t1.left, t2.left)
t1.right = merge_tree(t1.right, t2.right)
return t1

[@EmersonSridhar]

Questions stating we had to overlap is very confusing, but your solution was easy to follow thanks!

[@geraldmaboshe3014]

I think the statement "You need to merge the two trees into a new binary tree" does not mean creating a separate tree. So the below should work:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if not root1:
return root2
if not root2:
return root1
root1.val += root2.val
root1.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.right)
return root1

[@lily_h-m7j]

whats the time complexity for your solution?

[@geraldmaboshe3014]

That would be O(n) where n is the number of overlapping nodes

[@craftd8025]

This was pretty much my solution too. Yes still technically O(n), but there's no point continuing to traverse through a subtree when the other is Null

[@shelllu6888]

Hey! First and foremost, your videos are brilliantly curated! Honestly the best code-learning resources I've explored so far! ) I have a small suggestion, could we add a leetcode `easy`/`medium`/`hard` tag in the video title, so that we could know the difficulty of the problem before watching a video? Might because I'm a rookie learner and want to work on easy ones before harder ones, and I couldn't tell by the titles. Thanks!!

[@EverythingTechWithMustafa]

Use the difficulty playlist. Easy problems are all put into the EASY playlist

[@bestsaurabh]

Isn’t the time complexity O( max (n,m))??
Since we are traversing both the trees simultaneously

[@Abhi-qi6wm]

won't it be O(m*(|m-n|)) cause you're traversing the remaining nodes.

[@JoeZoll]

@@Abhi-qi6wm That's what I'm thinking, I wrote O(M + (N - M)))

[@kiranraaj7889]

@@JoeZoll O(M+(N-M)) is O(N) if you open the brackets, ignoring the fact we have to assume N for the tree with more nodes. which means TC is O(max(N,M)) if we dont assume.

[@danielsun716]

For me, I won't easily think of the base case of "if not root1 and not root2". probably should be like this, and it will reduce so many judge conditions:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if not root1:
return root2
if not root2:
return root1
v1 = root1.val
v2 = root2.val
root = TreeNode(v1 + v2)
root.left = self.mergeTrees(root1.left, root2.left)
root.right = self.mergeTrees(root1.right, root2.right)
return root

[@szetyngtyng]

for your base cases, where one of the roots is None and you just return the other root right away - what if the other root has more children under it? then wouldn't the solution be incorrect, since you are not merging those children in?

[@danielsun716]

@@szetyngtyng I think your question has answered your question. If root2 has more children under it, root1 is None, then we just merge it to root.left or root.right since we are doing that recursively. And we did merge them together. have you seen root.left = self.mergeTrees, and root.right = self.mergeTrees?
And if the recursive function doesn't trigger the base case to stop, then root1 and root2 won't be None. If any of them is None, then we just return any one of the base case. That's it.

[@jinkuanmoo5978]

@@danielsun716 what if root2 has more than 1 depth (for eg 2) than root1? In this case, the 1st extra depth will indeed be merged as "if not root1: return root2" will take care of it, but then the recursion should stop right there and leave the 2nd extra depth of root2 unmerged. (Although this is not the case when i run your code on LC as it came out with the correct answer, but I just couldn't understand how it is achieved

[@danielsun716]

@@jinkuanmoo5978 if you draw a pic, you will see what happens. what you worried is only the current recursion, not the upper recursion. So the case as you said, the recursion just stopped the recursion in root.left or root.right. If the root.left is stopped, then it went to root.right. If root.right is over, then it return the current node.

[@hamoodhabibi7026]

WOW i never thought about doing an if statement inside the traversal parameters lol

[@clck10]

Here is a functional extension to an arbitrary number of trees to be merged. It makes the code a bit cleaner, at the cost of changing the function signature. The main idea is using map and getattr to clean things up:
class Solution:
#def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
def mergeTrees(self, *args: Optional[List[TreeNode]]) -> Optional[TreeNode]:
# base case, all the trees are empty. return none
if not any(args):
return None
# get all of their values and sum them to make the new base node
vals = map(lambda r: getattr(r, 'val', 0), args)
root = TreeNode(sum(vals))
# merge the left subtrees
root.left = self.mergeTrees(*map(lambda r: getattr(r, 'left', None), args))
# merge the right subtrees
root.right = self.mergeTrees(*map(lambda r: getattr(r, 'right', None), args))
# return the new, merged tree
return root

[@michaelyao9389]

What if both are null, should I return an empty node TreeNode()?

[@stormarrow2120]

Null ptr is what the problem says i think. So if python, return None.

[@js2000honda]

Why isn’t the time complexity Max(m,n)?

[@vinoddiwan5792]

we need to check for both if one not exists then we take 0.
So why max ?????

[@zainrizvi6890]

can someone explain how this incorporates DFS? i understand how it works but it doesn't use the dfs function itself right?

[@kiranraaj7889]

it still is traversing each node depth wise, hence, dfs

[@thanosreddy3322]

DFS doesn't mean you should definitely use the dfs function. Here, the mergeTrees function is traversing the tree depth-wise, so itself is a dfs function

[@ganeshjaggineni4097]

NICE SUPER EXCELLENT MOTIVATED

[@useryyyfdgfd]

it's very easy but my teacher make it complicate, thank's for video

[@kareemsakr41]

Youre amazing

[@kullayibalaji1051]

How many of you are from india

[@omarllama]

You won't find a lot of Indians on this comment section, because this is "easy" haha.

[@CodingWorld202]

bro is indian..