Breadth First or Level Order Traversal¶

Helper functions¶

• Print elements at each level
• Get height of a tree

In [8]:

def print_elements_at_level(root, level):
    if root is None:
        return
    if level == 1:
        print(root.data)
    else:
        print_elements_at_level(root.left, level - 1)
        print_elements_at_level(root.right, level - 1)

def print_elements_at_level(root, level): if root is None: return if level == 1: print(root.data) else: print_elements_at_level(root.left, level - 1) print_elements_at_level(root.right, level - 1)

In [9]:

def get_height(root):

    # if tree is empty
    # or you have reached a leaf node
    if root is None:
        return 0

    # since there is no way to know in advance
    # which sub tree is going be deeper
    # so we calculate the height of both
    left_height = get_height(root.left)
    right_height = get_height(root.right)

    # now whichever subtree has more height
    # we return that
    # + 1 is done so as to increment the count from 0
    # because at the end when we reach the leaf node
    # we return 0
    if left_height > right_height:
        return left_height + 1
    else:
        return right_height + 1

def get_height(root): # if tree is empty # or you have reached a leaf node if root is None: return 0 # since there is no way to know in advance # which sub tree is going be deeper # so we calculate the height of both left_height = get_height(root.left) right_height = get_height(root.right) # now whichever subtree has more height # we return that # + 1 is done so as to increment the count from 0 # because at the end when we reach the leaf node # we return 0 if left_height > right_height: return left_height + 1 else: return right_height + 1

Tree Traversal Class¶

In [10]:

class TreeTraversal:
    @staticmethod
    def print_level_order_traversal_recursive(root):
        height = get_height(root)
        for i in range(1, height + 1):
            print_elements_at_level(root, i)

    @staticmethod
    def level_order_traversal_iterative(root):

        if root is None:
            print("Cannot traverse an empty tree")
            return

        bfs_elements = []
        queue = []

        # insert first element or root into the queue
        queue.append(root)

        while len(queue) > 0:

            # pop the element from the front of the queue
            node = queue.pop(0)
            bfs_elements.append(node.data)

            if node.left is not None:
                queue.append(node.left)

            if node.right is not None:
                queue.append(node.right)
        return bfs_elements

class TreeTraversal: @staticmethod def print_level_order_traversal_recursive(root): height = get_height(root) for i in range(1, height + 1): print_elements_at_level(root, i) @staticmethod def level_order_traversal_iterative(root): if root is None: print("Cannot traverse an empty tree") return bfs_elements = [] queue = [] # insert first element or root into the queue queue.append(root) while len(queue) > 0: # pop the element from the front of the queue node = queue.pop(0) bfs_elements.append(node.data) if node.left is not None: queue.append(node.left) if node.right is not None: queue.append(node.right) return bfs_elements

Construct a Tree¶

In [11]:

from utils.nodes import BinaryTreeNode as Node

from utils.nodes import BinaryTreeNode as Node

In [12]:

# Inherited base BinaryTreeNode class
# just for clarity but not required
class BinaryTree(Node):
    pass

# Inherited base BinaryTreeNode class # just for clarity but not required class BinaryTree(Node): pass

In [13]:

root = BinaryTree(1)
root.left = Node(2)
root.left.left = Node(3)
root.left.right = Node(4)
root.left.right.left = Node(5)

root.right = Node(6)
root.right.left = Node(7)
root.right.right = Node(8)

root = BinaryTree(1) root.left = Node(2) root.left.left = Node(3) root.left.right = Node(4) root.left.right.left = Node(5) root.right = Node(6) root.right.left = Node(7) root.right.right = Node(8)

Level Order Traversal¶

In [14]:

TreeTraversal.level_order_traversal_iterative(root)

TreeTraversal.level_order_traversal_iterative(root)

Out[14]:

[1, 2, 6, 3, 4, 7, 8, 5]