FilesExpand file tree

master

/

binary_tree_traversals.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

181 lines (136 loc) · 4.66 KB

master

/

binary_tree_traversals.py

Copy path

Top

File metadata and controls

• Code
• Blame

181 lines (136 loc) · 4.66 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

# https://en.wikipedia.org/wiki/Tree_traversal

from __future__ import annotations

from collections import deque

from dataclasses import dataclass

from typing import Any, Sequence

@dataclass

class Node:

data: int

left: Node | None = None

right: Node | None = None

def make_tree() -> Node | None:

return Node(1, Node(2, Node(4), Node(5)), Node(3))

def preorder(root: Node | None) -> list[int]:

"""

Pre-order traversal visits root node, left subtree, right subtree.

>>> preorder(make_tree())

[1, 2, 4, 5, 3]

"""

return [root.data] + preorder(root.left) + preorder(root.right) if root else []

def postorder(root: Node | None) -> list[int]:

"""

Post-order traversal visits left subtree, right subtree, root node.

>>> postorder(make_tree())

[4, 5, 2, 3, 1]

"""

return postorder(root.left) + postorder(root.right) + [root.data] if root else []

def inorder(root: Node | None) -> list[int]:

"""

In-order traversal visits left subtree, root node, right subtree.

>>> inorder(make_tree())

[4, 2, 5, 1, 3]

"""

return inorder(root.left) + [root.data] + inorder(root.right) if root else []

def height(root: Node | None) -> int:

"""

Recursive function for calculating the height of the binary tree.

>>> height(None)

0

>>> height(make_tree())

3

"""

return (max(height(root.left), height(root.right)) + 1) if root else 0

def level_order(root: Node | None) -> Sequence[Node | None]:

"""

Returns a list of nodes value from a whole binary tree in Level Order Traverse.

Level Order traverse: Visit nodes of the tree level-by-level.

"""

output: list[Any] = []

if root is None:

return output

process_queue = deque([root])

while process_queue:

node = process_queue.popleft()

output.append(node.data)

if node.left:

process_queue.append(node.left)

if node.right:

process_queue.append(node.right)

return output

def get_nodes_from_left_to_right(

root: Node | None, level: int

) -> Sequence[Node | None]:

"""

Returns a list of nodes value from a particular level:

Left to right direction of the binary tree.

"""

output: list[Any] = []

def populate_output(root: Node | None, level: int) -> None:

if not root:

return

if level == 1:

output.append(root.data)

elif level > 1:

populate_output(root.left, level - 1)

populate_output(root.right, level - 1)

populate_output(root, level)

return output

def get_nodes_from_right_to_left(

root: Node | None, level: int

) -> Sequence[Node | None]:

"""

Returns a list of nodes value from a particular level:

Right to left direction of the binary tree.

"""

output: list[Any] = []

def populate_output(root: Node | None, level: int) -> None:

if root is None:

return

if level == 1:

output.append(root.data)

elif level > 1:

populate_output(root.right, level - 1)

populate_output(root.left, level - 1)

populate_output(root, level)

return output

def zigzag(root: Node | None) -> Sequence[Node | None] | list[Any]:

"""

ZigZag traverse:

Returns a list of nodes value from left to right and right to left, alternatively.

"""

if root is None:

return []

output: list[Sequence[Node | None]] = []

flag = 0

height_tree = height(root)

for h in range(1, height_tree + 1):

if not flag:

output.append(get_nodes_from_left_to_right(root, h))

flag = 1

else:

output.append(get_nodes_from_right_to_left(root, h))

flag = 0

return output

def main() -> None: # Main function for testing.

"""

Create binary tree.

"""

root = make_tree()

"""

All Traversals of the binary are as follows:

"""

print(f"In-order Traversal: {inorder(root)}")

print(f"Pre-order Traversal: {preorder(root)}")

print(f"Post-order Traversal: {postorder(root)}", "\n")

print(f"Height of Tree: {height(root)}", "\n")

print("Complete Level Order Traversal: ")

print(level_order(root), "\n")

print("Level-wise order Traversal: ")

for level in range(1, height(root) + 1):

print(f"Level {level}:", get_nodes_from_left_to_right(root, level=level))

print("\nZigZag order Traversal: ")

print(zigzag(root))

if __name__ == "__main__":

import doctest

doctest.testmod()

main()