Leetcode - All Elements in Two Binary Search Trees (Python)

September 2020 Leetcode Challenge
Leetcode - All Elements in Two Binary Search Trees

[janmichaelaustria]

was trying to figure out how to merge two sorted lists in one pass! totally forgot about this!

thanks again tim!

[udayptp]

Remember don't trust me, I know nothing 😂

[siddharthsingh]

we can use this, just a bit modification to the merge sort technique =>
S1, S2, result = [], [], []
while root1 != None or root2 != None or len(S1) > 0 or len(S2) > 0:
#append only the left part
while root1 != None:
S1.append(root1)
root1 = root1.left
#append only the left part
while root2 != None:
S2.append(root2)
root2 = root2.left
if len(S2) == 0 or (len(S1) > 0 and S1[-1].val <= S2[-1].val):
#when encounter None the pop the element and
#append it to results and then move to the right
root1 = S1.pop()
result.append(root1.val)
root1 = root1.right
#when encountering None then pop the element and
#append it to results and then move to the right
else:
root2 = S2.pop()
result.append(root2.val)
root2 = root2.right

return result