Diagonal Traversal of a Binary Tree in Kotlin

by

Diagonal traversal of a binary tree is a way to visit all the nodes of a binary tree in a diagonal order. In diagonal traversal, we first visit the left child of the root node, then all the nodes on the diagonal starting from the left child of the root, and then we move to the right child of the root and repeat the process.

To be more precise, diagonal traversal of a binary tree starts with the leftmost node of the root node’s left subtree. Then we move one diagonal to the right and visit all the nodes on that diagonal until we reach the rightmost node of the tree. Then we move to the right child of the root and start a new diagonal.

Here is an example of diagonal traversal of a binary tree:

        8
      /   \
    3      10
  /   \      \
 1     6      14
     /  \    /
    4    7  13

The diagonal traversal of the above tree will be: [8, 10, 14, 3, 6, 7, 13, 1, 4]

Note that in the above example, we first visited the left child of the root node, which is 3, then we moved one diagonal to the right and visited all the nodes on that diagonal which are 6 and 14. Then we moved to the right child of the root which is 10 and started a new diagonal which consists of the nodes 7 and 13. Finally, we visited the leftmost node of the root node’s left subtree which is 1, followed by the node 4 which is on the diagonal that starts from the node 6.

Kotlin
fun diagonalTraversal(root: TreeNode?) {
    if (root == null) return

    val queue = LinkedList<TreeNode>()
    queue.offer(root)

    while (queue.isNotEmpty()) {
        val node = queue.poll()
        var diagonalNode = node

        while (diagonalNode != null) {
            print("${diagonalNode.value} ")
            if (diagonalNode.left != null) {
                queue.offer(diagonalNode.left)
            }
            diagonalNode = diagonalNode.right
        }
    }
}

The diagonalTraversal function takes the root of the binary tree as input, and performs diagonal traversal of the tree. The function first checks if the root is null, and if so, it returns. Otherwise, it creates a queue to hold the nodes of the tree, and adds the root node to the queue using the offer function.

The function then enters a loop that continues until the queue is empty. In each iteration of the loop, it dequeues a node from the queue using the poll function, and sets it as the current diagonal node.

It then enters another loop that continues until the current diagonal node is null. In each iteration of this loop, it prints the value of the current diagonal node, and checks if the left child of the diagonal node is not null. If so, it adds the left child to the queue using the offer function. It then moves to the right child of the current diagonal node, and sets it as the new current diagonal node.

Kotlin
import java.util.LinkedList

data class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun diagonalTraversal(root: TreeNode?) {
    if (root == null) return

    val queue = LinkedList<TreeNode>()
    queue.offer(root)

    while (queue.isNotEmpty()) {
        val node = queue.poll()
        var diagonalNode = node

        while (diagonalNode != null) {
            print("${diagonalNode.value} ")
            if (diagonalNode.left != null) {
                queue.offer(diagonalNode.left)
            }
            diagonalNode = diagonalNode.right
        }
    }
}

fun main() {
    /*
               8
             /   \
            3     10
           / \     \
          1   6     14
             / \   /
            4   7 13
    */
    val root = TreeNode(8)
    root.left = TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7)))
    root.right = TreeNode(10, null, TreeNode(14, TreeNode(13)))

    diagonalTraversal(root)
}

The main function creates a binary tree and calls the diagonalTraversal function to perform diagonal traversal of the tree. The binary tree used in the example is the same as the one used in the explanation of diagonal traversal above.

Output : 8 10 14 3 6 7 13 1 4

Leave a Comment