Zig Zag Traversal of Binary Tree in Kotlin | Snack Traversal

Zigzag traversal of a binary tree is a way of visiting the nodes of the tree in a zigzag pattern. It means that we first visit the nodes at level 1 from left to right, then the nodes at level 2 from right to left, and so on. Essentially, we alternate between left-to-right and right-to-left order at each level of the binary tree.

For example, consider the following binary tree:

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

A normal level-order traversal of this tree would visit the nodes in the following order: 1, 2, 3, 4, 5, 6, 7. However, a zigzag traversal of this tree would visit the nodes in the following order: 1, 3, 2, 4, 5, 6, 7.

Zigzag traversal is also known as a “snake” traversal because the pattern of the traversal looks like a snake moving back and forth across the tree.

Here’s a Kotlin code for performing a zigzag traversal of a binary tree:

import java.util.LinkedList

This will import the LinkedList class from the java.util package and make it available for use in your code.

fun zigzagTraversal(root: TreeNode?) {
    if (root == null) return
    
    val queue = LinkedList<TreeNode>()
    queue.add(root)
    
    var isReverse = false
    
    while (queue.isNotEmpty()) {
        val levelSize = queue.size
        val levelValues = mutableListOf<Int>()
        
        for (i in 0 until levelSize) {
            val node = queue.poll()
            
            if (isReverse) {
                levelValues.add(0, node.value)
            } else {
                levelValues.add(node.value)
            }
            
            node.left?.let { queue.add(it) }
            node.right?.let { queue.add(it) }
        }
        
        println(levelValues)
        isReverse = !isReverse
    }
}

In this code, we use a LinkedList as our queue data structure to store the nodes of the tree in level-order traversal. We start by adding the root node to the queue, and then we perform a loop until the queue is empty.

For each level of the tree, we first get the size of the queue at the beginning of the loop, which tells us how many nodes are in the current level. We then create an empty list called levelValues to store the values of the nodes in the current level.

We then perform another loop for each node in the current level. We poll the node from the queue, and if isReverse is true, we insert the value of the node at the beginning of the levelValues list (i.e., we reverse the order). Otherwise, we append the value of the node to the end of the levelValues list.

Finally, we add the left and right children of the node to the queue (if they exist), and then move on to the next node in the level. Once we’ve finished processing all nodes in the level, we print out the levelValues list, which contains the values of the nodes in that level in the correct order (either left-to-right or right-to-left, depending on the value of isReverse).

After processing all levels of the tree, we should have printed out the values of the nodes in zigzag order.

import java.util.LinkedList
data class TreeNode(var value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun zigzagTraversal(root: TreeNode?) {
    if (root == null) return
    
    val queue = LinkedList<TreeNode>()
    queue.add(root)
    
    var isReverse = false
    
    while (queue.isNotEmpty()) {
        val levelSize = queue.size
        val levelValues = mutableListOf<Int>()
        
        for (i in 0 until levelSize) {
            val node = queue.poll()
            
            if (isReverse) {
                levelValues.add(0, node.value)
            } else {
                levelValues.add(node.value)
            }
            
            node.left?.let { queue.add(it) }
            node.right?.let { queue.add(it) }
        }
        
        println(levelValues)
        isReverse = !isReverse
    }
}
fun main() {
    /*
        Create the following binary tree:
              1
            /   \
           2     3
          / \   / \
         4   5 6   7
    */
    val 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)

    println("Zigzag traversal:")
    zigzagTraversal(root)
}

This code creates a binary tree with the structure shown in the comment, and then calls the zigzagTraversal function with the root of the tree. The output of the program should be:

Zigzag traversal:
[1]
[3, 2]
[4, 5, 6, 7]

which is the zigzag order of the nodes in the tree.