FilesExpand file tree

master

/

P65_BreadthFirstTraversal.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

51 lines (42 loc) · 1.18 KB

master

/

P65_BreadthFirstTraversal.py

Copy path

Top

File metadata and controls

• Code
• Blame

51 lines (42 loc) · 1.18 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

# Author: OMKAR PATHAK

# Breadth First Traversal is the one in which we print the data level wise. Refer below code and output for more

# explanation

class Node(object):

def __init__(self, data = None):

self.leftChild = None

self.rightChild = None

self.data = data

def height(node):

if node is None:

return 0

else:

leftHeight = height(node.leftChild)

rightHeight = height(node.rightChild)

if leftHeight > rightHeight:

return leftHeight + 1

else:

return rightHeight + 1

def breadthFirstTraversal(root):

if root == None:

return 0

else:

h = height(root)

for i in range(h + 1):

printBFT(root, i)

def printBFT(root, level):

if root is None:

return

else:

if level == 1:

print(root.data, end = ' ')

elif level > 1:

printBFT(root.leftChild, level - 1)

printBFT(root.rightChild, level - 1)

if __name__ == '__main__':

root = Node(1)

root.leftChild = Node(2)

root.rightChild = Node(3)

root.leftChild.leftChild = Node(4)

breadthFirstTraversal(root)

# OUTPUT:

# 1 2 3 4