Binary Tree using array in Kotlin

by

A binary tree can be represented using an array by assigning each node in the tree a unique index based on its level and position within the level. The root node is assigned index 1, and its left and right children are assigned indices 2 and 3, respectively. The left child of a node at index i is located at index 2*i, while its right child is located at index 2*i + 1.

For example, consider the following binary tree:

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

We can represent this tree using an array as follows:

[1, 2, 3, 4, 5, 6, 7]

In this representation, the root node with value 1 is located at index 0, the left child with value 2 is located at index 1, the right child with value 3 is located at index 2, and so on.

This array representation of a binary tree is useful when we need to perform operations such as searching, insertion or deletion in the tree, since it allows us to access nodes using simple arithmetic calculations on the node indices. However, this representation can waste space in the array for sparse trees where there are many null or empty nodes.

Kotlin
class BinaryTreeArray<T : Comparable<T>>(size: Int) {
    private val tree = arrayOfNulls<Any?>(size)
    
    fun insert(value: T) {
        var i = 0
        while (tree[i] != null) {
            val nodeValue = tree[i] as T
            i = if (value < nodeValue) 2 * i + 1 else 2 * i + 2
        }
        tree[i] = value
    }
    
    fun search(value: T): Boolean {
        var i = 0
        while (i < tree.size && tree[i] != null) {
            val nodeValue = tree[i] as T
            if (nodeValue == value) {
                return true
            }
            i = if (value < nodeValue) 2 * i + 1 else 2 * i + 2
        }
        return false
    }
}

In this implementation, the binary tree is represented using an array of size size. The insert function inserts a new value into the tree by traversing the array until it finds an empty slot. The search function performs a binary search of the tree by comparing the value to be searched with the values in the array and traversing the array accordingly.

Note that this implementation assumes that the values in the binary tree are unique, since it does not handle cases where duplicate values are inserted.

Kotlin
class BinaryTreeArray<T : Comparable<T>>(size: Int) {
    private val tree = arrayOfNulls<Any?>(size)
    
    fun insert(value: T) {
        var i = 0
        while (tree[i] != null) {
            val nodeValue = tree[i] as T
            i = if (value < nodeValue) 2 * i + 1 else 2 * i + 2
        }
        tree[i] = value
    }
    
    fun search(value: T): Boolean {
        var i = 0
        while (i < tree.size && tree[i] != null) {
            val nodeValue = tree[i] as T
            if (nodeValue == value) {
                return true
            }
            i = if (value < nodeValue) 2 * i + 1 else 2 * i + 2
        }
        return false
    }
}

fun main() {
    val tree = BinaryTreeArray<Int>(10)
    tree.insert(5)
    tree.insert(2)
    tree.insert(7)
    tree.insert(1)
    tree.insert(3)
    tree.insert(6)
    tree.insert(8)
    println(tree.search(3)) // prints true
    println(tree.search(4)) // prints false
}

In this example, we create a BinaryTreeArray object with a maximum size of 10, and insert several integer values into the tree using the insert function. We then use the search function to check if the values 3 and 4 are present in the tree, and print the results to the console. The output should be:

Leave a Comment