Tree in Kotlin | Data Structures

Tree is a widely used abstract data type (ADT)—or data structure implementing this ADT—that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

A tree data structure can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root.

I do know that Computer science people are mad, that is the reason why they have an inverted tree and still, they call it a tree.tree-data-structure-kotlin

Tree Terminology

When working with trees, there are some terms that are worth becoming familiar with:tree-data-structure-with-nodes

  • Root: The initial node of the tree, where all the operations start.
  • Node: Any single item in the tree, usually a key-value item.
  • Child: A node directly connected to another node when moving away from the root.
  • Parent: The converse notion of a child.
  • Siblings: Nodes which are children of the same parent are called siblings
  • Leaf: The node, which does not have any children is called Leaf.
  • Link: Links is nothing but the arrow, we draw between two nodes.
  • Fruit: Unfortunately, this tree does not produce any fruits

tree-data-structure-with-nodesIn above Image:

  • 1 is the Root
  • 2, 3 are siblings and children of 1
  • 4,5,6 are sibling and children of 2 and Grandchildren of 1
  • 9,10 are children of 5, 9,10 does not have any children so we can call them as leaves
  • Ancestor : 1 is the ancestor of 2,3.
  • Descendant : 2,3 are descendants of 1, so on it goes for all nodes

Let's create the Milk Tree

tree-data-structure-normal-life

class TreeNode<T>(value:T){
    var value:T = value
    var parent:TreeNode<T>? = null

    var children:MutableList<TreeNode<T>> = mutableListOf()

    fun addChild(node:TreeNode<T>){
        children.add(node)
        node.parent = this
    }
    override fun toString(): String {
        var s = "${value}"
        if (!children.isEmpty()) {
            s += " {" + children.map { it.toString() } + " }"
        }
        return s
    }
}
fun main(args: Array<String>) {
    val milkTree = TreeNode<String>( "Milk")
    val beveragesNode = TreeNode<String>( "Beverages")
    val curdNode = TreeNode<String>( "Curd")
    milkTree.addChild(beveragesNode)
    milkTree.addChild(curdNode)

    val teaNode = TreeNode<String>( "tea")
    val coffeeNode = TreeNode<String>( "coffee")
    val milkShakeNode = TreeNode<String>( "Milk Shake")
    beveragesNode.addChild(teaNode)
    beveragesNode.addChild(coffeeNode)
    beveragesNode.addChild(milkShakeNode)

    val gingerTeaNode = TreeNode<String>( "ginger tea")
    val normalTeaNode = TreeNode<String>( "normal tea")
    teaNode.addChild(gingerTeaNode)
    teaNode.addChild(normalTeaNode)

    val yogurtNode = TreeNode<String>( "yogurt")
    val lassiNode = TreeNode<String>( "lassi")
    curdNode.addChild(yogurtNode)
    curdNode.addChild(lassiNode)

    println(milkTree)
}

Depth and Height of Tree

Height of a node is nothing but the number of nodes present from the leaf to the given node. Here the given node is not included but leaf Node is included.

Height is measured in an upward direction. Height is calculated by traversing from the deepest possible leaf to the given node. The longest path from the leaf to the root is called the height of a tree.

Depth of Node is the number of nodes present from the root node to a given node (considered the longest path when more than one path is present). The Root is included and the given node is not included in the calculation. Depth is always measured in a downward direction. The length of the path from the root to the end is called the depth of the tree.

A root node will have a depth of 0. Depth is calculated from traversal from root to the given node. Height of the tree is always the height of the Root Node.

Links are not calculated in the calculation


In below, Image the height and depth of the 5th node are: Depth = 5 and Height = 1tree-data-structure-with-nodes-depth-and height

Types of Tree

There few types of trees present in data structures, we will explore few of them:

  • Binary Tree
  • Binary Search Tree
  • AVL tree
  • Red-Black tree
  • Splay tree
  • N-ary tree
  • Trie Structure
  • Suffix tree
  • Huffman Tree
  • Heap Structure

Advantages of Tree

  • The Tree reflects structural relationships in the data.
  • It is used to represent hierarchies.
  • It provides efficient insertion and searching operations.
  • Trees are flexible. It allows to move subtrees around with minimum effort.
  • Manipulate sorted lists of data.
  • Router algorithms
  • Form of a multi-stage decision-making
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions