How to Implement Binary Search Tree in Kotlin: Simple Guide

To implement a binary search tree in Kotlin, define a Node class with left and right children and a value. Then create functions to insert values and traverse the tree, maintaining the order property where left child values are smaller and right child values are larger.

Syntax

A binary search tree (BST) node typically has three parts: a value, a left child, and a right child. You define a Node class with these properties. The tree itself manages insertion and traversal methods to keep the BST property intact.

• value: holds the data
• left: points to the left child node (values smaller than current)
• right: points to the right child node (values larger than current)

kotlin

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

class BinarySearchTree {
    var root: Node? = null

    fun insert(value: Int) {
        root = insertRec(root, value)
    }

    private fun insertRec(current: Node?, value: Int): Node {
        if (current == null) {
            return Node(value)
        }
        if (value < current.value) {
            current.left = insertRec(current.left, value)
        } else if (value > current.value) {
            current.right = insertRec(current.right, value)
        }
        return current
    }
}

Example

This example shows how to create a binary search tree, insert values, and print them in order (sorted). The inOrderTraversal function visits nodes from smallest to largest.

kotlin

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

class BinarySearchTree {
    var root: Node? = null

    fun insert(value: Int) {
        root = insertRec(root, value)
    }

    private fun insertRec(current: Node?, value: Int): Node {
        if (current == null) {
            return Node(value)
        }
        if (value < current.value) {
            current.left = insertRec(current.left, value)
        } else if (value > current.value) {
            current.right = insertRec(current.right, value)
        }
        return current
    }

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

fun main() {
    val bst = BinarySearchTree()
    bst.insert(50)
    bst.insert(30)
    bst.insert(70)
    bst.insert(20)
    bst.insert(40)
    bst.insert(60)
    bst.insert(80)

    print("In-order traversal: ")
    bst.inOrderTraversal(bst.root)
}

Output

In-order traversal: 20 30 40 50 60 70 80 

Common Pitfalls

Common mistakes when implementing a binary search tree include:

• Not handling null nodes properly, causing crashes.
• Inserting duplicate values without rules, which can break the BST property.
• Forgetting to update child links after recursive insertions.
• Mixing up left and right child comparisons.

Always check for null before accessing children and decide how to handle duplicates (ignore or store).

kotlin

/* Wrong: Not updating child links */
private fun insertRec(current: Node?, value: Int): Node {
    if (current == null) {
        return Node(value)
    }
    if (value < current.value) {
        insertRec(current.left, value) // Missing assignment back to current.left
    } else if (value > current.value) {
        insertRec(current.right, value) // Missing assignment back to current.right
    }
    return current
}

/* Right: Assign returned node to child */
private fun insertRec(current: Node?, value: Int): Node {
    if (current == null) {
        return Node(value)
    }
    if (value < current.value) {
        current.left = insertRec(current.left, value)
    } else if (value > current.value) {
        current.right = insertRec(current.right, value)
    }
    return current
}

Quick Reference

• Node class: holds value, left, and right children
• Insert: recursively place smaller values left, larger right
• Traversal: in-order traversal prints sorted values
• Null checks: always check for null before accessing children
• Duplicates: decide policy (ignore or handle specially)

Key Takeaways

Define a Node class with value, left, and right properties to represent tree nodes.

Insert values recursively, placing smaller values to the left and larger to the right.

Always update child links after recursive insertions to maintain tree structure.

Use in-order traversal to visit nodes in sorted order.

Handle null nodes carefully and decide how to treat duplicate values.