Binary Search Tree in Kotlin

by

A binary search tree (BST) is a data structure that is commonly used in computer science for efficient searching, insertion, and deletion operations. A BST is a binary tree where each node has at most two child nodes, and the left child is less than the parent node, and the right child is greater than the parent node.

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

The TreeNode class represents a single node in the BST. It has a value property, which stores the value of the node, and left and right properties, which are references to the left and right child nodes, respectively.

Kotlin
fun insert(root: TreeNode?, value: Int): TreeNode {
    if (root == null) {
        return TreeNode(value)
    }
    if (value < root.value) {
        root.left = insert(root.left, value)
    } else if (value > root.value) {
        root.right = insert(root.right, value)
    }
    return root
}

The insert function takes a root node and a value to insert into the BST. If the root node is null, then we create a new TreeNode with the given value and return it. If the value is less than the value of the root node, then we recursively insert the value into the left subtree. Otherwise, we recursively insert the value into the right subtree.

To traverse a BST, we can use the following three methods:

Kotlin
fun inOrderTraversal(root: TreeNode?) {
    if (root != null) {
        inOrderTraversal(root.left)
        print("${root.value} ")
        inOrderTraversal(root.right)
    }
}

In-order traversal: In this traversal, we visit the left subtree, then the current node, and then the right subtree.

Kotlin
fun preOrderTraversal(root: TreeNode?) {
    if (root != null) {
        print("${root.value} ")
        preOrderTraversal(root.left)
        preOrderTraversal(root.right)
    }
}

Pre-order traversal: In this traversal, we visit the current node, then the left subtree, and then the right subtree.

Kotlin
fun postOrderTraversal(root: TreeNode?) {
    if (root != null) {
        postOrderTraversal(root.left)
        postOrderTraversal(root.right)
        print("${root.value} ")
    }
}

Post-order traversal: In this traversal, we visit the left subtree, then the right subtree, and then the current node.

Kotlin
class TreeNode(var value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}
fun insert(root: TreeNode?, value: Int): TreeNode {
    if (root == null) {
        return TreeNode(value)
    }
    if (value < root.value) {
        root.left = insert(root.left, value)
    } else if (value > root.value) {
        root.right = insert(root.right, value)
    }
    return root
}
fun inOrderTraversal(root: TreeNode?) {
    if (root != null) {
        inOrderTraversal(root.left)
        print("${root.value} ")
        inOrderTraversal(root.right)
    }
}
fun preOrderTraversal(root: TreeNode?) {
    if (root != null) {
        print("${root.value} ")
        preOrderTraversal(root.left)
        preOrderTraversal(root.right)
    }
}
fun postOrderTraversal(root: TreeNode?) {
    if (root != null) {
        postOrderTraversal(root.left)
        postOrderTraversal(root.right)
        print("${root.value} ")
    }
}
fun main() {
    val root = TreeNode(5)
    insert(root, 2)
    insert(root, 7)
    insert(root, 1)
    insert(root, 3)
    insert(root, 6)
    insert(root, 8)

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

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

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

Leave a Comment