Boundary traversal of a binary tree in Kotlin

Boundary traversal of a binary tree involves visiting the boundary nodes of the tree in a clockwise direction, starting from the root node. The boundary nodes of a tree include the root node, the left boundary, the leaf nodes, and the right boundary.

Here’s an example of a binary tree :

            20
          /    \
         8     22
       /   \    /   \
     4     12  21    24
         /  \
        10   14

The boundary traversal of this tree in a clockwise direction would be: 20 8 4 10 14 21 24 22.

Note that the root node is always included in the boundary traversal, and the left boundary and right boundary are also included. However, only the leaf nodes that are on the leftmost or rightmost path of the tree are included in the boundary traversal.

To implement the boundary traversal of a binary tree, we can break down the traversal into three parts:

1. Traverse the left boundary of the tree from the root to the leftmost leaf node.
2. Traverse all the leaf nodes of the tree in a left-to-right order.
3. Traverse the right boundary of the tree from the root to the rightmost leaf node.

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

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

    // Don't print leaf nodes in this step
    if (root.left != null) {
        print("${root.value} ")
        printLeftBoundary(root.left)
    } else if (root.right != null) {
        print("${root.value} ")
        printLeftBoundary(root.right)
    }
}

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

    // Don't print leaf nodes in this step
    if (root.right != null) {
        printRightBoundary(root.right)
        print("${root.value} ")
    } else if (root.left != null) {
        printRightBoundary(root.left)
        print("${root.value} ")
    }
}

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

    if (root.left == null && root.right == null) {
        print("${root.value} ")
    }

    printLeaves(root.left)
    printLeaves(root.right)
}

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

    print("${root.value} ")
    printLeftBoundary(root.left)
    printLeaves(root.left)
    printLeaves(root.right)
    printRightBoundary(root.right)
}

1. Node class: This is the basic class used to represent a node in a binary tree. It contains the data stored in the node, and two pointers to its left and right children.
2. printBoundaryNodes function: This function prints the boundary nodes of a binary tree in anti-clockwise order. It takes a reference to the root node of the tree as its input and calls the printLeftBoundaryNodes, printLeafNodes, and printRightBoundaryNodes functions in order.
3. printLeftBoundaryNodes function: This function prints the left boundary nodes of a binary tree in top-down order. It takes a reference to the root node of the tree as its input and prints the data of the root node, followed by the left boundary nodes of the left subtree, recursively, and finally the left boundary nodes of the right subtree, recursively.
4. printLeafNodes function: This function prints the leaf nodes of a binary tree in left to right order. It takes a reference to the root node of the tree as its input and prints the data of the leaf nodes using an in-order traversal.
5. printRightBoundaryNodes function: This function prints the right boundary nodes of a binary tree in bottom-up order. It takes a reference to the root node of the tree as its input and prints the data of the right boundary nodes of the right subtree, recursively, followed by the data of the right boundary nodes of the left subtree, recursively, and finally the data of the root node.
6. isLeafNode function: This function checks whether a given node is a leaf node or not. It takes a reference to a node as its input and returns true if the node is a leaf node (i.e., has no left or right child), and false otherwise.

Overall, the printBoundaryNodes function calls the printLeftBoundaryNodes, printLeafNodes, and printRightBoundaryNodes functions to print the left boundary nodes, leaf nodes, and right boundary nodes of the binary tree, respectively, in the desired order.

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

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

    // Don't print leaf nodes in this step
    if (root.left != null) {
        print("${root.value} ")
        printLeftBoundary(root.left)
    } else if (root.right != null) {
        print("${root.value} ")
        printLeftBoundary(root.right)
    }
}

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

    // Don't print leaf nodes in this step
    if (root.right != null) {
        printRightBoundary(root.right)
        print("${root.value} ")
    } else if (root.left != null) {
        printRightBoundary(root.left)
        print("${root.value} ")
    }
}

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

    if (root.left == null && root.right == null) {
        print("${root.value} ")
    }

    printLeaves(root.left)
    printLeaves(root.right)
}

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

    print("${root.value} ")
    printLeftBoundary(root.left)
    printLeaves(root.left)
    printLeaves(root.right)
    printRightBoundary(root.right)
}

fun main() {
    /*
                20
              /    \
             8     22
           /   \    /   \
         4     12  21    24
             /  \
            10   14
    */
    val root = TreeNode(20)
    root.left = TreeNode(8, TreeNode(4), TreeNode(12, TreeNode(10), TreeNode(14)))
    root.right = TreeNode(22, TreeNode(21), TreeNode(24))

    boundaryTraversal(root)
}

1. The main function starts by creating a sample binary tree with seven nodes and arbitrary data values.
2. It then calls the printBoundaryNodes function, passing the root node of the binary tree as an argument.
3. The printBoundaryNodes function, in turn, calls the printLeftBoundaryNodes, printLeafNodes, and printRightBoundaryNodes functions in the desired order to print the boundary nodes of the binary tree.
4. Finally, the main function exits, having printed the boundary nodes of the binary tree in anti-clockwise order.

Output : 20 8 4 10 14 21 24 22