Reverse Level Order Traversal in Spiral Form

Updated: at 03:34 AM

Reverse level order traversal is a technique to traverse a tree data structure in the reverse order of levels, starting from the last level towards the root. Combining it with spiral traversal adds an additional twist - traversing each level in a spiral or zigzag fashion. This combines the reverse level order and spiral traversal approaches to print the nodes of a tree in an interesting spiral pattern across levels from bottom to top.

In this comprehensive guide, we will learn how to implement reverse level order traversal in spiral form in Python.

Table of Contents

Open Table of Contents

Overview

Reverse level order traversal traverses a tree from the lowest level to the root. For a binary tree, it starts from the last level, prints all nodes in that level from left to right, then moves to the second last level printing nodes from right to left, and continues alternating between left to right and right to left printing for higher levels until it reaches the root node.

Spiral traversal prints nodes of a tree in a zigzag or spiral fashion - traversing left to right first, then right to left in alternative rows. Combining spiral order traversal logic while traversing the reverse levels of a tree gives us the reverse level order traversal in spiral form technique.

The key ideas are:

This results in nodes being printed in a unique spiral pattern across increasing levels from bottom up.

Applications

Some applications of reverse level order traversal in spiral form include:

The spiral order adds visual appeal and can aid in understanding the reverse level order flow. This technique can be applied to binary, n-ary, and general tree structures.

Implementation in Python

We will implement reverse level order traversal in spiral form in Python using the following steps:

  1. Define a tree node class
  2. Create a tree data structure (binary tree used here)
  3. Initialize an empty result list to store nodes
  4. Define a recursive method for spiral traversal
  5. Append nodes to result list in spiral order
  6. Call spiral traversal method starting from bottom level
  7. Return result list with nodes in reverse level order spiral form

1. Define Tree Node Class

We define a simple TreeNode class to represent nodes in our tree:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

The node contains a value and pointers to left and right child nodes.

2. Create Sample Binary Tree

         1
      /     \
     2       3
   /  \     /  \
  4    5   6    7

We can create this sample binary tree in Python:

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

This forms the sample binary tree structure shown above with 7 nodes.

3. Initialize Empty Result List

We need a result list to store the nodes while traversing:

result = []

4. Define Recursive Spiral Traversal Method

We define a recursive method spiralTraversal to traverse the tree in spiral order:

def spiralTraversal(root, level, direction):
  if root:
    # append current node to result
    result.append(root.val)

    if level % 2 == 0:
      # traverse left to right
      spiralTraversal(root.left, level+1, 1)
      spiralTraversal(root.right, level+1, 1)
    else:
      # traverse right to left
      spiralTraversal(root.right, level+1, 0)
      spiralTraversal(root.left, level+1, 0)

It takes the root node, level number, and direction as inputs.

If the current level is even, it traverses left to right by calling the method recursively on the left subtree first, then right subtree.

If the level is odd, it traverses right to left by calling right then left subtree.

The node’s value is appended to the result list before the recursive calls.

5. Append Nodes in Spiral Order

To print the spiral traversal, we call this method starting from the tree bottom:

spiralTraversal(root, 0, 0)

This will append the node values to result in spiral order traversing bottom-up.

6. Call from Bottom Level

To make it reverse level order, we find the tree height first:

height = max_depth(root)

Then call the spiral traversal beginning from the lowest level:

for i in range(height, -1, -1):
  spiralTraversal(root, i, 0)

This loops from tree height down to the root level (0).

7. Return Reverse Level Order Spiral Result

Finally, we return the populated result list containing node values in reverse level order spiral form:

return result

Complete Code

The complete Python code is:

class TreeNode:
  def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right

# Recursive spiral traversal
def spiralTraversal(root, level, direction):

  if root:

    # Append node value
    result.append(root.val)

    if level % 2 == 0:
      # Traverse left to right
      spiralTraversal(root.left, level+1, 1)
      spiralTraversal(root.right, level+1, 1)

    else:
      # Traverse right to left
      spiralTraversal(root.right, level+1, 0)
      spiralTraversal(root.left, level+1, 0)

# Reverse level order traversal
def reverseSpiral(root):

  result = []
  height = max_depth(root)

  for i in range(height, -1, -1):
    spiralTraversal(root, i, 0)

  return result

Time and Space Complexity

The space can be optimized to O(1) by printing instead of storing in list.

Summary

Key points:

Reverse level order spiral traversal combines two interesting traversal approaches to give a unique sequence. It can be applied to any tree structure and provides an alternative way to process hierarchical data in Python.