+ 1

How do I output a reversed binary Tree in Python (recursive)

Here is my question on StackOverflow --> https://stackoverflow.com/questions/65249988/inverting-binary-tree-in-JUMP_LINK__&&__python__&&__JUMP_LINK-recursive Problem: I have a binary tree in front of me: 4 2 7 1 3 6 9 Now I want to output the mirrored version meaning: 4 7 2 9 6 3 1 My pseudo code: #def invert_tree(nodes, root) #Stopping recursion if tree is empty #swap left subtree with right subtree #invert left subtree #invert right subtree But I have no idea how to implement the code. Can you guys help me out?

11th Dec 2020, 11:55 AM
Max_Mnemo
Max_Mnemo - avatar
8 Antworten
+ 2
Here' s both was list comp and recursive: tree = [[4], [7, 2], [1, 3, 6, 9]] newlist1 = [x[::-1] for x in tree] print(newlist1) newlist2 = [] def reverse_tree(lst): if not lst: return newlist2.append(lst.pop(0)[::-1]) reverse_tree(lst) reverse_tree(tree) print(newlist2)
11th Dec 2020, 2:58 PM
rodwynnejones
rodwynnejones - avatar
11th Dec 2020, 12:22 PM
Иван Чикyнов
Иван Чикyнов - avatar
+ 2
Thanks guys for all the great answers. @rodwynnejones @Ipang
11th Dec 2020, 3:03 PM
Max_Mnemo
Max_Mnemo - avatar
+ 1
Have you though about list comprehension.? Not sure how that impacts the time complexity though. edit......ahh I see.... recursively..sorry.
11th Dec 2020, 1:28 PM
rodwynnejones
rodwynnejones - avatar
+ 1
Don't know about complexity, but I just have a working recursion function, different in signature to your pseudo code though. But it works for the given example (haven't tested using other data). Includes an iterative sample based on rodwynnejones' idea https://code.sololearn.com/c6tmHG9l3iSC/?ref=app
11th Dec 2020, 2:35 PM
Ipang
0
@Иван Чикyнов Thank you very much I'm still kinda sceptical that this a good solution because you are using two for-loops meaning the time complexity will be O(n^2). I learned as a rule of thumb that using nested for-loops is bad practise. But your solution does indeed solve the problem. Thanks again.
11th Dec 2020, 12:40 PM
Max_Mnemo
Max_Mnemo - avatar
0
I agree this is a bit of a bad decision, but the main thing is that it works
11th Dec 2020, 1:00 PM
Иван Чикyнов
Иван Чикyнов - avatar
0
@Иван Чикyнов Yeah, that's true.
11th Dec 2020, 1:05 PM
Max_Mnemo
Max_Mnemo - avatar