DEV Community

WolfOf420Stret
WolfOf420Stret

Posted on • Edited on

3 1 1

Trees in Kotlin: A Comprehensive Guide 🌳

Table of Contents

  1. Introduction
  2. What Even Is a Tree?
  3. Basic Tree Concepts
  4. Binary Trees Deep Dive
  5. Binary Trees Vs Binary Search Trees
  6. Core Operations
  7. Tree Traversal: The Grand Tour
  8. AVL Trees: The Yoga Masters
  9. B-Trees: The Database Darlings
  10. Search Algorithms
  11. Advanced Implementation and Best Practices
  12. Performance Comparison
  13. Common Interview Questions
  14. Final Thoughts: The Forest for the Trees

Introduction

Remember playing "family tree" as a kid? Well, welcome to the grown-up version, where instead of arguing about who gets to be the cool aunt, we're organizing data in the most efficient way possible. Trees in computer science are like family trees on steroids – they're hierarchical, they're powerful, and they definitely won't ask to borrow money.

What Even Is a Tree? (And No, We're Not Arguing About Botany)

In programming, a tree is made up of nodes. Think of it like a family tree, but instead of awkward Thanksgiving dinners, you get neat, logical relationships. Here's the breakdown:

  • Root: The OG node. The Beyoncé of the tree. Everything starts here.
  • Parent/Child: Nodes can have children (like the root), and children can have their own children. Basically, it's a never-ending cycle of responsibility.
  • Leaf: A node with no children. The introvert of the tree. Just wants to be left alone.
  • Node : A fundamental unit containing data and references to other nodes
  • Edge: The connection between nodes
  • Height : The length of the longest path from root to leaf
  • Depth : The length of the path from a node to the root
  • Subtree : A tree consisting of a node and all its descendants

If you're picturing an upside-down oak tree with numbers instead of acorns, you're on the right track.

tree

Basic Tree Concepts

Let's start with the basics (because even Olympic athletes had to learn to walk first):

data class TreeNode<T>(
    val value: T,
    val children: MutableList<TreeNode<T>> = mutableListOf()
) {
    fun addChild(value: T): TreeNode<T> {
        val child = TreeNode(value)
        children.add(child)
        return child
    }

    fun removeChild(value: T) {
        children.removeIf { it.value == value }
    }
    fun findChild(value: T): TreeNode<T>? {
        if (this.value == value) return this

        for (child in children) {
            val found = child.findChild(value)
            if (found != null) return found
        }
        return null
    }

}
Enter fullscreen mode Exit fullscreen mode

Binary Trees Deep Dive

Binary trees are like having kids with a strict two-child policy. Each node can have at most two children, making them perfect for divide-and-conquer scenarios.

data class BinaryNode<T>(
    val value: T,
    var left: BinaryNode<T>? = null,
    var right: BinaryNode<T>? = null
) {
    fun isLeaf() = left == null && right == null
    fun hasSingleChild() = left == null xor right == null
    fun hasChildren() = left != null || right != null
}
Enter fullscreen mode Exit fullscreen mode

Binary Trees Vs Binary Search Trees

A BST is a binary tree with additional ordering properties:

  • All nodes in the left subtree must be less than the current node
  • All nodes in the right subtree must be greater than the current node
  • No duplicate values allowed (in most implementations)
class BinarySearchTree<T : Comparable<T>> {
    private var root: BinaryNode<T>? = null

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

    private fun insertRec(node: BinaryNode<T>?, value: T): BinaryNode<T> {
        if (node == null) return BinaryNode(value)

        when {
            value < node.value -> node.left = insertRec(node.left, value)
            value > node.value -> node.right = insertRec(node.right, value)
            else -> return node // Duplicate values not allowed
        }
        return node
    }

    fun find(value: T): BinaryNode<T>? {
        var current = root
        while (current != null) {
            when {
                value < current.value -> current = current.left
                value > current.value -> current = current.right
                else -> return current
            }
        }
        return null
    }

    fun delete(value: T) {
        root = deleteRec(root, value)
    }

    private fun deleteRec(node: BinaryNode<T>?, value: T): BinaryNode<T>? {
        if (node == null) return null

        when {
            value < node.value -> node.left = deleteRec(node.left, value)
            value > node.value -> node.right = deleteRec(node.right, value)
            else -> {
                // Node with only one child or no child
                if (node.left == null) return node.right
                if (node.right == null) return node.left

                // Node with two children: Get the inorder successor (smallest
                // in the right subtree)
                node.value = minValue(node.right!!)
                node.right = deleteRec(node.right, node.value)
            }
        }
        return node
    }

    private fun minValue(node: BinaryNode<T>): T {
        var current = node
        while (current.left != null) {
            current = current.left!!
        }
        return current.value
    }
}
Enter fullscreen mode Exit fullscreen mode

Core Operations

Insertion

  1. Binary Tree: Can insert at any available position
  2. BST: Must maintain ordering property
  • Compare with current node
  • Go left if smaller
  • Go right if larger
  • Create new node when null position is found

Searching

  1. Binary Tree: Must check all nodes (O(n))
  2. BST: Can use ordering to optimize (O(log n) average case)
  • Compare with current node
  • Go left if smaller
  • Go right if larger
  • Return null if not found

Deletion

  1. Binary Tree: Simply remove node and restructure
  2. BST: Three cases:
  • Leaf node: Simply remove
  • One child: Replace with child
  • Two children: Replace with inorder successor (smallest in right subtree)

Tree Traversal: The Grand Tour

Think of tree traversal as being a tourist in a tree-shaped city. There are several ways to explore:

1. Depth-First Search (DFS) Variants

class TreeTraversal<T> {
    // Pre-order: Root → Left → Right
    fun preorderTraversal(root: BinaryNode<T>?, result: MutableList<T> = mutableListOf()): List<T> {
        root?.let {
            result.add(it.value)
            preorderTraversal(it.left, result)
            preorderTraversal(it.right, result)
        }
        return result
    }

    // In-order: Left → Root → Right
    fun inorderTraversal(root: BinaryNode<T>?, result: MutableList<T> = mutableListOf()): List<T> {
        root?.let {
            inorderTraversal(it.left, result)
            result.add(it.value)
            inorderTraversal(it.right, result)
        }
        return result
    }

    // Post-order: Left → Right → Root
    fun postorderTraversal(root: BinaryNode<T>?, result: MutableList<T> = mutableListOf()): List<T> {
        root?.let {
            postorderTraversal(it.left, result)
            postorderTraversal(it.right, result)
            result.add(it.value)
        }
        return result
    }

    // Iterative In-order traversal (because recursion isn't always the answer)
    fun iterativeInorderTraversal(root: BinaryNode<T>?): List<T> {
        val result = mutableListOf<T>()
        val stack = Stack<BinaryNode<T>>()
        var current = root

        while (current != null || stack.isNotEmpty()) {
            // Reach the leftmost node of the current node
            while (current != null) {
                stack.push(current)
                current = current.left
            }

            // Current is now null, pop an element from stack
            current = stack.pop()
            result.add(current.value)

            // Move to the right subtree
            current = current.right
        }
        return result
    }
}
Enter fullscreen mode Exit fullscreen mode

2. Breadth-First Search (BFS)

When you want to explore level by level, like a proper tourist:

fun <T> levelOrderTraversal(root: BinaryNode<T>?): List<List<T>> {
    val result = mutableListOf<List<T>>()
    if (root == null) return result

    val queue = LinkedList<BinaryNode<T>>()
    queue.offer(root)

    while (queue.isNotEmpty()) {
        val levelSize = queue.size
        val currentLevel = mutableListOf<T>()

        repeat(levelSize) {
            val node = queue.poll()
            currentLevel.add(node.value)

            node.left?.let { queue.offer(it) }
            node.right?.let { queue.offer(it) }
        }
        result.add(currentLevel)
    }
    return result
}
Enter fullscreen mode Exit fullscreen mode

tree traversal

AVL Trees: The Yoga Masters

AVL trees are binary search trees that do yoga every morning to stay balanced. They maintain their balance by ensuring that the heights of the left and right subtrees of any node differ by at most one.

data class AVLNode<T : Comparable<T>>(
    val value: T,
    var left: AVLNode<T>? = null,
    var right: AVLNode<T>? = null,
    var height: Int = 1
) {
    val balanceFactor: Int
        get() = (left?.height ?: 0) - (right?.height ?: 0)

    fun updateHeight() {
        height = maxOf(left?.height ?: 0, right?.height ?: 0) + 1
    }
}

class AVLTree<T : Comparable<T>> {
    private var root: AVLNode<T>? = null

    private fun rotateRight(y: AVLNode<T>): AVLNode<T> {
        val x = y.left!!
        val T2 = x.right

        x.right = y
        y.left = T2

        y.updateHeight()
        x.updateHeight()

        return x
    }

    private fun rotateLeft(x: AVLNode<T>): AVLNode<T> {
        val y = x.right!!
        val T2 = y.left

        y.left = x
        x.right = T2

        x.updateHeight()
        y.updateHeight()

        return y
    }

    fun insert(value: T) {
        root = insert(root, value)
    }

    private fun insert(node: AVLNode<T>?, value: T): AVLNode<T> {
        // Standard BST insert
        if (node == null) return AVLNode(value)

        when {
            value < node.value -> node.left = insert(node.left, value)
            value > node.value -> node.right = insert(node.right, value)
            else -> return node // Duplicate values not allowed
        }

        // Update height of current node
        node.updateHeight()

        // Get balance factor and balance if needed
        return when (node.balanceFactor) {
            2 -> { // Left heavy
                if ((node.left?.balanceFactor ?: 0) < 0) {
                    node.left = rotateLeft(node.left!!)
                }
                rotateRight(node)
            }
            -2 -> { // Right heavy
                if ((node.right?.balanceFactor ?: 0) > 0) {
                    node.right = rotateRight(node.right!!)
                }
                rotateLeft(node)
            }
            else -> node
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

AVL Tree rotation

B-Trees: The Database Darlings

B-Trees are the backbone of database indexing. Unlike binary trees, they can have multiple keys per node and multiple children. They're like those big family reunions where everyone somehow fits at the table.

B Trees

data class BTreeNode<K : Comparable<K>, V>(
    val keys: MutableList<K> = mutableListOf(),
    val values: MutableList<V> = mutableListOf(),
    val children: MutableList<BTreeNode<K, V>> = mutableListOf(),
    var isLeaf: Boolean = true
) {
    fun insertNonFull(key: K, value: V, degree: Int) {
        var i = keys.size - 1

        if (isLeaf) {
            // Find location to insert and move all greater keys up
            while (i >= 0 && keys[i] > key) {
                keys.add(i + 1, keys[i])
                values.add(i + 1, values[i])
                i--
            }
            keys.add(i + 1, key)
            values.add(i + 1, value)
        } else {
            // Find child which is going to have the new key
            while (i >= 0 && keys[i] > key) i--

            if (children[i + 1].keys.size == 2 * degree - 1) {
                splitChild(i + 1, children[i + 1], degree)
                if (keys[i + 1] < key) i++
            }
            children[i + 1].insertNonFull(key, value, degree)
        }
    }

    private fun splitChild(i: Int, y: BTreeNode<K, V>, degree: Int) {
        val z = BTreeNode<K, V>(isLeaf = y.isLeaf)

        // Copy the last (t-1) keys of y to z
        for (j in 0 until degree - 1) {
            z.keys.add(y.keys[j + degree])
            z.values.add(y.values[j + degree])
        }

        // Copy the last t children of y to z
        if (!y.isLeaf) {
            for (j in 0 until degree) {
                z.children.add(y.children[j + degree])
            }
        }

        // Insert new child in this node
        children.add(i + 1, z)

        // Move middle key to this node
        keys.add(i, y.keys[degree - 1])
        values.add(i, y.values[degree - 1])

        // Remove keys and children from y
        for (j in y.keys.size - 1 downTo degree - 1) {
            y.keys.removeAt(j)
            y.values.removeAt(j)
        }
        if (!y.isLeaf) {
            for (j in y.children.size - 1 downTo degree) {
                y.children.removeAt(j)
            }
        }
    }
}

class BTree<K : Comparable<K>, V>(private val degree: Int) {
    private var root: BTreeNode<K, V> = BTreeNode()

    fun insert(key: K, value: V) {
        val r = root
        if (r.keys.size == 2 * degree - 1) {
            val s = BTreeNode<K, V>(isLeaf = false)
            root = s
            s.children.add(r)
            s.splitChild(0, r, degree)
            s.insertNonFull(key, value, degree)
        } else {
            r.insertNonFull(key, value, degree)
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Search Algorithms

Let's look at different ways to find our data (because sometimes it likes to play hide and seek):

Binary Search Tree Search

fun <T : Comparable<T>> BinaryNode<T>.search(value: T): BinaryNode<T>? {
    return when {
        this.value == value -> this
        value < this.value -> left?.search(value)
        else -> right?.search(value)
    }
}
Enter fullscreen mode Exit fullscreen mode

Advanced Search Patterns

class TreeSearcher<T : Comparable<T>> {
    // Find closest value in BST
    fun findClosest(root: BinaryNode<T>?, target: T): T? {
        var closest: T? = null
        var minDiff: Int? = null
        var current = root

        while (current != null) {
            val currentDiff = abs(current.value.compareTo(target))
            if (minDiff == null || currentDiff < minDiff) {
                closest = current.value
                minDiff = currentDiff
            }

            current = when {
                target < current.value -> current.left
                target > current.value -> current.right
                else -> return current.value // Exact match found
            }
        }

        return closest
    }

    // Find kth smallest element
    fun findKthSmallest(root: BinaryNode<T>?, k: Int): T? {
        val stack = Stack<BinaryNode<T>>()
        var current = root
        var count = 0

        while (current != null || stack.isNotEmpty()) {
            while (current != null) {
                stack.push(current)
                current = current.left
            }

            current = stack.pop()
            count++

            if (count == k) {
                return current.value
            }

            current = current.right
        }

        return null
    }
}
Enter fullscreen mode Exit fullscreen mode

Advanced Implementation and Best Practices

Memory Optimization

class CompactTree<T>(
    private val values: Array<T?>,
    private val size: Int
) {
    fun getLeft(index: Int) = 2 * index + 1
    fun getRight(index: Int) = 2 * index + 2
    fun getParent(index: Int) = (index - 1) / 2

    fun getValue(index: Int): T? =
        if (index < size) values[index] else null
}
Enter fullscreen mode Exit fullscreen mode

Thread Safety

class ThreadSafeTree<T> {
    private val lock = ReentrantReadWriteLock()
    private var root: TreeNode<T>? = null

    fun insert(value: T) {
        lock.writeLock().use {
            // Perform thread-safe insertion
        }
    }

    fun search(value: T): Boolean {
        lock.readLock().use {
            // Perform thread-safe search
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Performance Comparison

Operation BST (avg) BST (worst) AVL Tree B-Tree
Search O(log n) O(n) O(log n) O(log n)
Insert O(log n) O(n) O(log n) O(log n)
Delete O(log n) O(n) O(log n) O(log n)
Space O(n) O(n) O(n) O(n)

🌳 Real-World Analogies

  • AVL Rotations: Like adjusting a wobbly table—rotate legs until stable.

  • B-Tree Splitting: Similar to splitting an overpacked suitcase—take out the middle item (median) and distribute the rest.

Tree Traversals:

  • In-Order: Reading a book from left to right

  • Level-Order: Scanning a supermarket aisle shelf by shelf

  • Post-Order: Assembling furniture (build children first, then parent)

Common Interview Questions

Easy

Maximum Depth of Binary Tree

fun maxDepth(root: BinaryNode<T>?): Int {
    if (root == null) return 0
    return 1 + maxOf(maxDepth(root.left), maxDepth(root.right))
}

Enter fullscreen mode Exit fullscreen mode

Check if Binary Tree is Symmetric

fun isSymmetric(root: BinaryNode<T>?): Boolean {
    if (root == null) return true
    return isMirror(root.left, root.right)
}

private fun isMirror(left: BinaryNode<T>?, right: BinaryNode<T>?): Boolean {
    if (left == null && right == null) return true
    if (left == null || right == null) return false

    return (left.value == right.value) &&
           isMirror(left.left, right.right) &&
           isMirror(left.right, right.left)
}

Enter fullscreen mode Exit fullscreen mode

Medium

Validate Binary Search Tree

fun isValidBST(root: BinaryNode<T>?): Boolean {
    return isValidBST(root, null, null)
}

private fun isValidBST(
    node: BinaryNode<T>?,
    min: T?,
    max: T?
): Boolean {
    if (node == null) return true

    if ((min != null && node.value <= min) ||
        (max != null && node.value >= max)) {
        return false
    }

    return isValidBST(node.left, min, node.value) &&
           isValidBST(node.right, node.value, max)
}

Enter fullscreen mode Exit fullscreen mode

Lowest Common Ancestor

fun lowestCommonAncestor(
    root: BinaryNode<T>?,
    p: BinaryNode<T>,
    q: BinaryNode<T>
): BinaryNode<T>? {
    if (root == null || root == p || root == q) return root

    val left = lowestCommonAncestor(root.left, p, q)
    val right = lowestCommonAncestor(root.right, p, q)

    return when {
        left != null && right != null -> root
        left != null -> left
        else -> right
    }
}

Enter fullscreen mode Exit fullscreen mode

Hard

Serialize and Deserialize Binary Tree

class Codec {
    fun serialize(root: BinaryNode<String>?): String {
        if (root == null) return "null"
        return "${root.value},${serialize(root.left)},${serialize(root.right)}"
    }

    fun deserialize(data: String): BinaryNode<String>? {
        val nodes = LinkedList(data.split(","))
        return deserializeHelper(nodes)
    }

    private fun deserializeHelper(nodes: LinkedList<String>): BinaryNode<String>? {
        val value = nodes.removeFirst()
        if (value == "null") return null

        val node = BinaryNode(value)
        node.left = deserializeHelper(nodes)
        node.right = deserializeHelper(nodes)
        return node
    }
}

Enter fullscreen mode Exit fullscreen mode

💡 Pro Tips

  • Use AVL trees when you need frequent inserts/deletes with fast lookups

  • Choose B-trees for disk-based storage (they minimize disk I/O)

  • Prefer iterative traversal for deep trees to avoid stack overflow

  • Combine tree structures: Use a trie for autocomplete, then an AVL tree for sorting suggestions

🚀 When Trees Collide: Hybrid Structures

Modern systems often combine tree variants:

  • Databases use B-trees for storage and BSTs for in-memory indices

  • File systems might use tries for path lookup and AVL trees for metadata

  • Game engines employ spatial trees (like octrees) built using balancing techniques from AVL

🎓 Tree Wisdom

Trees teach us valuable programming lessons:

  • Balance is key (AVL)

  • Divide and conquer (B-tree splits)

  • Different perspectives matter (traversal orders)

  • Growth requires adaptation (balancing operations)

🔧 Debugging Tree Issues

Common pitfalls and solutions:

  • Infinite Loops: Check for missing parent pointers in rotations

  • Memory Leaks: Null out children references when deleting nodes

  • Balance Factor Errors: Always update heights after rotations

  • Incorrect Traversal Order: Double-check left/right recursion order

Final Thoughts: The Forest for the Trees

Trees are like the Swiss Army knife of data. Trees are more than data structures—they're a way of thinking hierarchically. Whether you're balancing AVL nodes like a tightrope walker or splitting B-tree nodes like a careful librarian, remember: every tree starts with a single root. Now go forth and branch out!

(But seriously, if your binary tree starts growing mushrooms, maybe check your recursion depth.)

Heroku

Build apps, not infrastructure.

Dealing with servers, hardware, and infrastructure can take up your valuable time. Discover the benefits of Heroku, the PaaS of choice for developers since 2007.

Visit Site

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more