Tree Traversal

The topic of today is Tree Traversal. A tree is a type of data structure that is hierarchically organized with elements that have specific relationships. Understanding trees, one of the commonly used data structures, and implementing basic traversal algorithms is very useful in coding tests. In this article, we will start with the basic concepts of trees, explore various traversal methods, and discuss the implementation in Kotlin.

1. Basic Concepts of Trees

A tree is a data structure composed of nodes. Each node can have values and child nodes. A tree can be described using the following key terms:

• Root Node: The topmost node of the tree.
• Leaf Node: A node that has no child nodes.
• Internal Node: A node that has child nodes.
• Subtree: A tree with a specific node as its root.

2. Types of Tree Traversal

Tree traversal methods can generally be divided into three types:

1. Pre-order Traversal: Visit the node – traverse the left subtree – traverse the right subtree
2. In-order Traversal: Traverse the left subtree – visit the node – traverse the right subtree
3. Post-order Traversal: Traverse the left subtree – traverse the right subtree – visit the node

3. Problem Description

Let’s assume we are given a binary tree as follows:

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

Please list the results of pre-order, in-order, and post-order traversals for this tree.

4. Problem Solving Process

The first requirement to solve this problem is to define a class structure for the tree. In Kotlin, we can implement the nodes of a binary tree in the following way:

4.1) Define the Binary Tree Node Class

class TreeNode(val value: Int) {
        var left: TreeNode? = null
        var right: TreeNode? = null
    }

The above class has a value that stores the node’s value and variables left and right that reference the left and right child nodes.

4.2) Implementing Pre-order Traversal

Pre-order traversal visits the node before visiting its children. The function for this is as follows:

fun preOrderTraversal(node: TreeNode?) {
        if (node == null) return
        print("${node.value} ")
        preOrderTraversal(node.left)
        preOrderTraversal(node.right)
    }

4.3) Implementing In-order Traversal

In-order traversal first visits the left child and then the current node. It can be implemented as follows:

fun inOrderTraversal(node: TreeNode?) {
        if (node == null) return
        inOrderTraversal(node.left)
        print("${node.value} ")
        inOrderTraversal(node.right)
    }

4.4) Implementing Post-order Traversal

Post-order traversal visits both children before visiting the current node. The implementation is as follows:

fun postOrderTraversal(node: TreeNode?) {
        if (node == null) return
        postOrderTraversal(node.left)
        postOrderTraversal(node.right)
        print("${node.value} ")
    }

5. Creating and Testing the Tree

Now let’s create the tree and test each traversal method. You can structure and execute the tree traversal with the following code:

fun main() {
        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)

        print("Pre-order Traversal: ")
        preOrderTraversal(root)
        println()

        print("In-order Traversal: ")
        inOrderTraversal(root)
        println()

        print("Post-order Traversal: ")
        postOrderTraversal(root)
        println()
    }

6. Code Execution Results

When executing the above program, you can obtain the following results:

Pre-order Traversal: 1 2 4 5 3 6 7 
In-order Traversal: 4 2 5 1 6 3 7 
Post-order Traversal: 4 5 2 6 7 3 1 

7. Summary

In this article, we learned the basic concepts of trees and the three methods of tree traversal: pre-order, in-order, and post-order. We implemented each traversal method in Kotlin and could understand the tree structure through a simple example that can be used in real situations. Since tree problems are frequently encountered in coding tests, it is important to practice sufficiently to become familiar with them.

8. Additional Practice Problems

Enhance your understanding of tree traversal by solving the following problems:

1. Write a function to calculate the depth of a given binary tree.
2. Write a function to find the maximum path sum in a binary tree.

9. Conclusion

Now that you have a basic understanding of tree structures and traversal methods, you are prepared to challenge yourself with more complex coding problems. As you solve various algorithm problems involving trees, continue to build your skills in this area. In the next lesson, we will cover graph search. Thank you!