Skip to content

Instantly share code, notes, and snippets.

@lopespm
Created April 6, 2019 12:24
Show Gist options
  • Save lopespm/993f0af88cf30b7f8c9e17982518b71b to your computer and use it in GitHub Desktop.
Save lopespm/993f0af88cf30b7f8c9e17982518b71b to your computer and use it in GitHub Desktop.
Prints a given tree in levels, using BFS - using Python
# Print tree by levels - using BFS
# The idea behind it is to use BFS and keep a level marker integer which marks the end the last node of the level. This is similar to Naresh's sentinel approach, but without the need of inserting a sentinel inside the queue, since this is accomplished by the level marker.
# Time complexity of O(n)
# Space complexity: O(2^tree_height)
from collections import deque
class Node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def print_levels_tree(root: Node):
q = deque()
q.append(root)
level, level_marker = 0, 1
while q:
if (level_marker == 0):
level, level_marker = level + 1, len(q)
print("", end = '\n')
level_marker -= 1
node = q.popleft()
if (node is None):
continue
print(node.data, "\t", end = '')
q.append(node.left)
q.append(node.right)
# Some examples
tree = Node(19, Node(7, Node(3), Node(11)), Node(19))
print_levels_tree(tree)
left = Node(7, Node(3, Node(2), Node(5)), Node(11, None, Node(17, Node(13))))
tree = Node(19, left, Node(43))
print_levels_tree(tree)
left = Node(7, Node(3, Node(2), Node(5)), Node(11, None, Node(17, Node(13))))
right = Node(43, Node(23, None, Node(37, Node(29, None, Node(31)), Node(41))), Node(47, None, Node(53)) )
tree = Node(19, left, right)
print_levels_tree(tree)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment