Python Day 23: BST Level-Order Traversal




A level-order traversal, also known as a breadth-first search, visits each level of a tree's nodes from left to right, top to bottom. You are given a pointer, root, pointing to the root of a binary search tree. Complete the levelOrder function provided in your editor so that it prints the level-order traversal of the binary search tree.



  1. import sys
  2. class Node:
  3. def __init__(self,data):
  4. self.right=self.left=None
  5. self.data = data
  6. class Solution:
  7. def insert(self,root,data):
  8. if root==None:
  9. return Node(data)
  10. else:
  11. if data<=root.data:
  12. cur=self.insert(root.left,data)
  13. root.left=cur
  14. else:
  15. cur=self.insert(root.right,data)
  16. root.right=cur
  17. return root
  18. from collections import deque
  19. def levelOrder(self,root):
  20. queue = self.deque([root]) if root else self.deque()
  21. while queue:
  22. node = queue.popleft()
  23. print(node.data, end=' ')
  24. if node.left: queue.append(node.left)
  25. if node.right: queue.append(node.right)
  26. T=int(input())
  27. myTree=Solution()
  28. root=None
  29. for i in range(T):
  30. data=int(input())
  31. root=myTree.insert(root,data)
  32. myTree.levelOrder(root)




codesadda.com

Codesadda.com is your home of programming solutions, tutorials, video tutorials and much more. Sign Up for our weekly newsletter to get update about new content.

Like us on Facebook | Connect with us on LinkedIn | Subscribe our Channel on Youtube