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.

When working with trees, there are some terms that are worth becoming familiar with:

**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

**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

```
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)
}
```

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 5^{th} node are: Depth = 5 and Height = 1

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

- 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