Level order traversal in the spiral form in Python

In this tutorial, we will learn about the Level order tree traversal in the spiral form in Python. This is the extended version of my previous tutorial Level order tree traversal. In this algorithm, we traverse the alternate levels of the tree in reverse order.

Level order traversal in Spiral form

Let us create a binary tree and try to level order traverse in spiral form. We start from the root node( 6 ) and traverse the nodes of level 1 from left to right. In contrast, we traverse level 2 nodes from right to left. Similarly, the alternate levels are traversed in reverse order.

class Tree:
    def __init__(node,data):
        node.data = data
        node.right = None
        node.left = None
    def node(node,data):
        if (node.data is None):
            node.data = data
        else:
            if( data < node.data ):
                if (node.left is None): 
                    node.left = Tree(data)
                else:
                    node.left.node(data)
            elif( data > node.data ):
                if ( node.right is None):
                    node.right = Tree(data)
                else:
                    node.right.node(data)

tree = Tree(6)
tree.node(4)
tree.node(5)
tree.node(8)
tree.node(2)
tree.node(9)
tree.node(1)
tree.node(3)
tree.node(7)

The Level order traversal of the above tree in the spiral form can be 6 4 8 2579 13 or 6 8 4 9 7 5 2 3 1. Let’s try to implement this in our code.

def height(node,tree):
    if (tree is None):
        return 0
    else:
        left = node.height(tree.left)
        right= node.height(tree.right)
        return max(left,right)+1
def Spiral(node,tree):
    temp = 0
    height = node.height(tree)
    for i in range(0,height):
        node.level_order(tree,i,temp)
        temp = not temp
def level_order(node,tree,level,temp):
    if (tree == None):
        return
    elif (level == 0):
        print(tree.data,end = ' ')
    elif (level > 0):
        if (temp == 1):
            node.level_order(tree.left,level-1,temp)
            node.level_order(tree.right,level-1,temp)
        else:
            node.level_order(tree.right,level-1,temp)
            node.level_order(tree.left,level-1,temp)

Explanation:

• For level order traversal, we have to find the height of the tree. Therefore we use a recursive function to find the height of the tree. In the function, we calculate the height of the left subtree and the right subtree and compare the values. As a result, we get the maximum height which is considered as the tree height.
• To traverse the alternate levels in reverse order, we have declared a variable ‘temp’. The ‘temp’ changes its value from 1 to 0 and 0 to 1 in every iteration. When the temp == 1, we traverse from left to right and when temp ==0, we traverse from right to left.
• As a result, in the above code, the tree is traversed in the order 6 4 8 2 5 7 9 1 using the recursive function.

Here is how the complete code should look like

class Tree:
    def __init__(node,data):
        node.data = data
        node.right = None
        node.left = None
    def node(node,data):
        if (node.data is None):
            node.data = data
        else:
            if( data < node.data ):
                if (node.left is None): 
                    node.left = Tree(data)
                else:
                    node.left.node(data)
            elif( data > node.data ):
                if ( node.right is None):
                    node.right = Tree(data)
                else:
                    node.right.node(data)
def height(node,tree):
    if (tree is None):
        return 0
    else:
        left = node.height(tree.left)
        right= node.height(tree.right)
        return max(left,right)+1
def Spiral(node,tree):
    temp = 0
    height = node.height(tree)
    for i in range(0,height):
        node.level_order(tree,i,temp)
        temp = not temp
def level_order(node,tree,level,temp):
    if (tree == None):
        return
    elif (level == 0):
        print(tree.data,end = ' ')
    elif (level > 0):
        if (temp == 1):
            node.level_order(tree.left,level-1,temp)
            node.level_order(tree.right,level-1,temp)
        else:
            node.level_order(tree.right,level-1,temp)
            node.level_order(tree.left,level-1,temp)


tree = Tree(6)
tree.node(4)
tree.node(5)
tree.node(8)
tree.node(2)
tree.node(9)
tree.node(1)
tree.node(3)
tree.node(7)
tree.Spiral(tree)

Output:

Level order traversal in the spiral form: 6 4 8 9 7 5 2 1 3

If you have any quires, please feel free to drop in your comments.
Thank you…🙂