## Tree in Kotlin | Data Structures

The 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 Terminology

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 that are children of the same parent are called siblings
• Leaf: The node, which does not have any children is called Leaf.
• Link: Links are nothing but the arrow, we draw between two nodes.
• Fruit: Unfortunately, this tree does not produce any fruits

In the 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

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

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

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")

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

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

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

println(milkTree)
}``````

## Depth and Height of Tree

The 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. The height of the tree is always the height of the Root Node.

Links are not calculated in the calculation

In the below, Image the height and depth of the 5th node are: Depth = 5 and Height = 1

## Types of Tree

There few types of trees present in data structures, we will explore a 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