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

Question

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?

Answer 1

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)

Answer 2

all ingenious is simple
https://code.sololearn.com/cHw2zy2gKDTD/?ref=app

Answer 3

Thanks guys for all the great answers. @rodwynnejones @Ipang

Answer 4

Have you though about list comprehension.?
Not sure how that impacts the time complexity though.

edit......ahh I see.... recursively..sorry.

Answer 5

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

Answer 6

@Иван Чик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.

Answer 7

I agree this is a bit of a bad decision, but the main thing is that it works

Answer 8

@Иван Чикyнов Yeah, that's true.