Zig-Zag Traversal of Binary Tree in Python

We will understand how to solve the problem of getting a binary tree's zig-zag level order traversal in this tutorial.

Example:

We have a binary tree like

We will see different approaches to creating a function that will print the zig-zag traversal of the given binary tree. The zig-zag traversal of the above binary tree will be 1 11 2 3 5 12 13 15 14 10 9 8 7 6 4

Approach - 1

The first approach to solving this problem is by using two stacks.

We will assume that the two stacks represent the current_level and the next_level. We will also be required to keep tracking the zig-zag level order of the current level, i.e., whether the traversal of the current level should be from left to right or from right to left. We will pop the nodes from the current_level stack and print the values of those nodes. When the traversal order of the current level is from left to right, we will push the nodes in the left to right order. First, we will push the left child and then the right child of the node to the next_level stack. Since the stack data structure has LIFO (Last In First Out) property, when we pop the nodes in the next loop, they will be arranged in the reverse order.

On the contrary, when the traversal order of the current level is from right to left, we will push the nodes from right to left, i.e., firstly, the right child, then the left child in the next_level stack. The final step will be to swap the current_level and the next_level stacks when we reach the level's end. The level will be completed when the current_level stack is empty.

Code

Output:

The zig-zag level order traversal of the binary tree is:
1 11 2 3 5 12 13  

Time Complexity: This algorithm has O(N) time complexity. We have used a linear loop to traverse the binary tree

Space Complexity: This algorithm takes O(N) extra memory space hence, the space complexity is O(N). We have used linear space to store the stack

Approach - 2

We used an iterative approach to solve the problem in the above example. This time we will use a recursion function. The approach is similar to another problem known as Level Order Traversal. The only difference between these two problems is that we must create an extra variable. This variable will keep track of the left-to-right and right-to-left orders.

Below is the Python program to implement this approach.

Code

Output:

The Zig-Zag Level Order traversal of the given binary tree is:
1 11 2 3 5 12 13 15 14 10 9 8 7 6 4 

Approach - 3

Here is another approach to solving this problem. We will use the queue data structure. For a quick introduction, the queue data structure follows the LIFO principle, i.e., Last In, First Out. We can use the deque class in the collections module to create the queue data structure, or we can simply create a Python list and apply the LIFO principle to the list. We will use the push and pop commands differently based on the traversal level. Below is the implementation of this approach.

Code

Output:

The Zig-Zag Level Order traversal of the given binary tree is:
1 11 2 3 5 12 13 15 14 10 9 8 7 6 4

Time Complexity: This algorithm has O(N) time complexity. N symbolizes the number of nodes present in the binary tree.

Auxiliary Space: The queue data structure takes O(N) space; hence the space complexity of this approach is O(N).

Approach - 4

This approach will use a ubiquitous algorithm called Depth First Search (DFS).

Below is the algorithmic approach of this program:

• We will start by defining a Python function that will take the input as the pointer pointing towards the root node of the binary tree, and it will return the zig-zag level order traversal of the given tree.
• Inside this function, we will initialize an empty Python list. This list will contain the nodes at every level of the tree.
• We will execute a modified version of the pre-order traversal of a binary tree using the Depth First Search algorithm. To execute this approach, we need to create another function which will be called recursively. This recursive function will take in the current node, the level of this node, and the ans array. In this function, if the level of the current node is either greater than or equal to the length of the ans array, then it will create a new array for the level of the current node in the ans array and append the current node to this array. Else, it will simply append the current node to the array for the current input level in the ans array. Then, this function will be called recursively first on the left subtree and then on the right subtree of the current input node. We will also increment the level by 1 for both subtrees while calling this function.
• When the traversal is over, we will reverse the order of the array present at the odd indices of the ans array. The list of these nodes is at the odd level of the binary tree and needs to follow right-to-left order. This way, we will get the zig-zag order level order traversal.

Below is the Python code that shows how to implement this approach.

Code

Output:

The zig-zag level order traversal of the binary tree is:
1 11 2 3 5 12 13 

Time Complexity: This algorithm has O(N) time complexity. N symbolizes the total number of non-null nodes present in the binary tree.

Auxiliary Space: This program takes O(H) extra memory space. H symbolizes the height of the given binary tree. O(H) space complexity is because we store the node values at each level in a different list.