Python/data_structures/binary_tree/basic_binary_tree.py at master · imanghotbi-python/Python · 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
from __future__ importannotations


classNode:
"""
 A Node has data variable and pointers to Nodes to its left and right.
 """

def__init__(self, data: int) ->None:
self.data=data
self.left: Node|None=None
self.right: Node|None=None


defdisplay(tree: Node|None) ->None: # In Order traversal of the tree
"""
 >>> root = Node(1)
 >>> root.left = Node(0)
 >>> root.right = Node(2)
 >>> display(root)
 0
 1
 2
 >>> display(root.right)
 2
 """
iftree:
display(tree.left)
print(tree.data)
display(tree.right)


defdepth_of_tree(tree: Node|None) ->int:
"""
 Recursive function that returns the depth of a binary tree.

 >>> root = Node(0)
 >>> depth_of_tree(root)
 1
 >>> root.left = Node(0)
 >>> depth_of_tree(root)
 2
 >>> root.right = Node(0)
 >>> depth_of_tree(root)
 2
 >>> root.left.right = Node(0)
 >>> depth_of_tree(root)
 3
 >>> depth_of_tree(root.left)
 2
 """
return1+max(depth_of_tree(tree.left), depth_of_tree(tree.right)) iftreeelse0


defis_full_binary_tree(tree: Node) ->bool:
"""
 Returns True if this is a full binary tree

 >>> root = Node(0)
 >>> is_full_binary_tree(root)
 True
 >>> root.left = Node(0)
 >>> is_full_binary_tree(root)
 False
 >>> root.right = Node(0)
 >>> is_full_binary_tree(root)
 True
 >>> root.left.left = Node(0)
 >>> is_full_binary_tree(root)
 False
 >>> root.right.right = Node(0)
 >>> is_full_binary_tree(root)
 False
 """
ifnottree:
returnTrue
iftree.leftandtree.right:
returnis_full_binary_tree(tree.left) andis_full_binary_tree(tree.right)
else:
returnnottree.leftandnottree.right


defmain() ->None: # Main function for testing.
tree=Node(1)
tree.left=Node(2)
tree.right=Node(3)
tree.left.left=Node(4)
tree.left.right=Node(5)
tree.left.right.left=Node(6)
tree.right.left=Node(7)
tree.right.left.left=Node(8)
tree.right.left.left.right=Node(9)

print(is_full_binary_tree(tree))
print(depth_of_tree(tree))
print("Tree is: ")
display(tree)


if__name__=="__main__":
main()