Tree Data Structures in Kotlin

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 a 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 scince people are mad, that is the reason why thy have inverted tree and stll they call it as 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 chidren of same parent are called as siblings
  • Leaf: The node, which doenot have any chidren is called Leaf.
  • Link: Links is nothing but the the arrow, we draw bet ween two nodes.
  • Fruit: Unfortunately, this tree does not produce any fruits
tree-data-structure-with-nodes In above Image:
  • 1 is the Root
  • 2, 3 are siblings and children of 1
  • 4,5,6 are sibling and children of 2 and Grand children of 1
  • 9,10 are children of 5, 9,10 doenot have any children so we can call them as leaves
  • Ancester : 1 is ancester of 2,3.
  • Descendent : 2,3 are descndents 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 he 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 upward direction. Height is calculated by traversing from the deepest possible leaf to the given node. The longest path from leaf to the root is called height of a tree.

Depth of Node is, the number of nodes present from he root node to given node (considerd the longest path when more than one path is present). Root is included and the given node is not included in the calculation. Depth is always measured in downward direction. The length of the path from root to the end is called 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 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 = 1 tree-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

  • Tree reflects structural relationships in the data.
  • It is used to represent hierarchies.
  • It provides an 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

aaaaaaaaaaaaa
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions

Recent Addition

new tutorial Selenium Online Training : Our next online training course for Selenium with Java starts from 17th December 2018.

You can attend first 3 classes for free, the total course fee is INR 10,000

The course time would be 8.00 PM(IST) for the first three classes

If you are interested to learn, then you can join the course by sending email to chercher.tech@gmail.com

or Register below


 
Join My Facebook Group
Join Group