article banner

Advent of Kotlin: Week 2

Good to see you again! I am back with a new challenge for you. We will continue with algorithmic problems, but this time we will be implementing some tree algorithms.

If you still haven't finished the previous week problem, no worries. You have time until the end of the year :)

Tree algorithms

Tree is an important data structure in computer science. It is used to keep elements, but thanks to the traits of this data structure, many operations can be faster than when those elements are kept in a list. A good example is Binary Search Tree, where we can find an element in O(log n) time, that is much better than O(n) time, that is needed if we search through a list. Tree algorithms are also very popular as a challange (both for fun and during interviews) because they give a lot of space for showing off the power of recursion.

There are different kind of trees, but what characterizes them is that they have nodes - elements, that might hold a value or references to other nodes. This makes a structure - one node can have multiple children (those references to other nodes), but only one parent. The parent of all nodes is called the root node. It is representing the whole tree, because with it we can access all other nodes.

In this excersise, we will operate on a very simple tree. Is intermediete nodes (Node) will have up to two childs and no values. Values will be stored in the node with no childs, called a Leaf. We will represent our data struture in the following way:

sealed class Tree<T> { override fun toString(): String = when (this) { is Leaf -> value.toString() is Node -> "($left, $right)" } } data class Leaf<T>(val value: T) : Tree<T>() data class Node<T>(val left: Tree<T>?, val right: Tree<T>?) : Tree<T>()

Your task is to implement the following functions:

  • countAll - that counts the number of leaves and nodes.
  • height - that returns the height of this tree, that is the number of elements between root and the furthest leaf, including root and this leaf.
  • biggest - that finds the biggest element kept by the leaf. This should be defined only for trees whose type parameter is comparable (implements Comparable<T>).
  • sum - that calculates the sum of elements in the Tree<Int>.
  • contains - that checks if a value elem is in any leaf on this tree.
  • plus - that creates a node with tree1 and tree2 as leaves.
  • toList - that converts this tree to a list.

All these functions should use recurrence, smart casting, and when structure. As an example, here is the implementation of count, that counts the number of leaves:

fun Tree<*>.count(): Int = when (this) { is Leaf -> 1 is Node -> left.count() + right.count() }

Here is the definition of the Tree class in the project:

https://github.com/MarcinMoskala/advent-2021/blob/master/src/main/kotlin/week2/Tree.kt

Here are unit tests:

https://github.com/MarcinMoskala/advent-2021/blob/master/src/test/kotlin/week2/TreeOperationsTest.kt

Notice, that you need to uncomment them first. It is because your task is also to create the functions you are to implement.

Ending

I wish you the best of luck in this and future challenges and can't wait to see your solutions :)