Algo/invert_binary_tree.py at master · AntiHero/Algo · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
from utils import bst

root = bst.BSTNode(10)
root.insert(5)
root.insert(15)
root.insert(5)
root.insert(8)
root.insert(6)
root.insert(2)
root.insert(1)
root.insert(22)
root.display()


# O(n) time | O(d) time, wher d - depth | O(lon(n))
def invert_binary_tree_recursively(tree):
    if tree is None:
        return
    tree.right, tree.left = tree.left, tree.right
    invert_binary_tree_recursively(tree.left)
    invert_binary_tree_recursively(tree.right)


invert_binary_tree_recursively(root)
print('\n')
root.display()


# O(n) time | O(n) space
def invert_binary_tree(tree):
    queue = [tree]

    while len(queue):
        current = queue.pop(0)
        if current is None:
            continue
        current.left, current.right = current.right, current.left
        queue.append(current.left)
        queue.append(current.right)


invert_binary_tree(root)
print('\n')
root.display()