## Data structures, Binary trees

So far we had seen linear structures, linked list, queues, stack, arrays, all of them are linear data structures with well defined operations. Trees are our first non-linear data structure and, as the name says, they are data structures that looks like a tree (or an inverted tree).

Each element in a tree is named a node and the first node, the node at the top, is named root, a node can have none or more children and each children has a parent, the “connections” between each node are called edges, nodes without children (with the exception of the root node) are called leaves, the number of edges from the root to a node is called the depth of the tree and the distance between the longest path of a node to the root is called the height of a node, so to know the height of a node or tree we count the number of nodes from that node to the root node (inclusive). In the image we see the node $$D$$ has a depth of 2 and the whole tree has a height of 4, nodes $$H$$, $$I$$, $$E$$, $$F$$ and $$G$$ are leaves. Depending on the maximum number of children per node we have different types of trees, the simplest is a tree where each node has a maximum of 2 children (binary trees) and we will be exploring them extensively in this and upcoming blog posts. There are trees where nodes have up to three children (ternary trees) and even 4 (quaternary) and 8 (octary) trees, in general we usually talk about $$n$$-trees but we will be limiting ourselves to binary trees for now.

A simple way to assemble a binary tree is with a simple structure to hold the data and references to its left and right children, something simple like this:

class Node<T>(
private val data: T,
private var left: Node<T>? = null,
private var right: Node<T>? = null
)


And we can represent a tree like the one shown in the image directly in code:

val root = Node('A',
Node('B',
Node('D',
Node('H'),
Node('I')),
Node('E')),
Node('C',
Node('F'),
Node('G'))
)
`

A full binary tree is a tree where all the nodes have two or no children at all, the tree in the example is a full tree. There is the concept of a complete tree but we will discuss that one when we see another structure related to trees, the heap. The maximum number of nodes in a full binary tree of $$l$$ levels is given by the equation $$2^l -1$$.

There are many properties of a tree that are useful when handling data, but for now try to represent a tree in your favourite language, as you see it is nothing fancy!