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. 

  3. class Node:

  4.     def __init__(self,data):

  5.         self.right=self.left=None

  6.         self.data = data

  7. class Solution:

  8.     def insert(self,root,data):

  9.         if root==None:

  10.             return Node(data)

  11.         else:

  12.             if data<=root.data:

  13.                 cur=self.insert(root.left,data)

  14.                 root.left=cur

  15.             else:

  16.                 cur=self.insert(root.right,data)

  17.                 root.right=cur

  18.         return root

  19. 

  20.     from collections import deque

  21.     def levelOrder(self,root):      

  22. 

  23.         queue = self.deque([root]) if root else self.deque()

  24. 

  25.         while queue:

  26.             node = queue.popleft()

  27.             print(node.data, end=' ')

  28. 

  29.             if node.left: queue.append(node.left)

  30.             if node.right: queue.append(node.right)

  31. 

  32. T=int(input())

  33. myTree=Solution()

  34. root=None

  35. for i in range(T):

  36.     data=int(input())

  37.     root=myTree.insert(root,data)

  38. myTree.levelOrder(root)
download android app