A tree can be defined as a hierarchical arrangement of nodes. The primary node is referred to as the root node, which branches out into various sub-nodes. The node that does not have any successor is known as the leafnode.

In Tree data items are stored such that:
a) There is special data item called the root of the tree.
b) Remaining data items are partitioned into number of mutually exclusive (i.e. disjoint) subsets, each of which is itself a tree. And they are called sub-trees. Some trees terminology and their description are given below:

1. Root: it is specially designed data item in a tree. It is the first in the hierarchical arrangement of data items. In the above tree, A is the root item.
2. Node: Each data item in a tree is called a node. It is the basic structure in a tree. It specifies the data information and links to other data items. There are 12 nodes in the above tree.
3. Degree of a node: It is a number of nodesadjacent to a given node. In the above tree, the degree of node A is 3, the degree of node C is 2.
4. Degree of a tree: It is the maximum degree of nodes in a given tree. In the above tree the node A has degree 3. In all this above is value is the maximum. So, the degree of the above tree is 4.
5. Terminal Node: A Node with degree 0 is called a terminal node or a leaf. In the above tree, there are 7 terminals nodes. They are E, J, G, H, K and L.
6. Non-Terminal Node: Any node except the root node whose degree is not 0 is called Non-Terminal Node.
7. Siblings: The children nodes of a given parent node are called siblings. They are also called brothers. In the above tree, E and F are siblings of parent node B. K and L are sibling’s parent node of I.
8. Level: The entire tree structure is leveled in such a way that the root node is always at level 0. Then its immediate children are at level 1 and their immediate children are at level 2 and so on. Up to the terminal nodes. In general, if a node is a level N, then its children will be at level N+1.
9. Edge: It is a connecting line of two nodes. That is the line drawn from one node to another node is called an edge.
10. Path: It is a sequence of consecutive edges from the source node to the destination node. In the above tree, the path between A and J is given by the node pairs. (A, B), (B, F) and (F, J).
11. Depth: It is the maximum level of any node in a given tree. In the above tree, the root node A has the maximum level. That is the number of levels 1 can descend the tree from its root to the terminal nodes (leaves). The term height is also used to denote the depth.
12. Forest: It is a set of disjoint trees. In a given tree, if you remove its root node then it becomes a forest. In the above tree, there is forest with three trees.

Binary tree
A Binary tree is a finite set of data items which is either empty or consists of a single item called the root and two disjoint binary trees called the left sub-tree and right sub-tree.
A binary tree is a very important and the most commonly used non-linear data structure.
In a binary tree the maximum degree of any node is at most two. That means there may be a 0 degree node or a 1 degree node and 2 degree node.

Strictly binary tree
If every non-terminal node in a binary tree consists of non empty left sub-tree and right sub-tree then such a tree is called strictly binary tree.
Traversal of a binary tree
Tree traversal is one of the most common operations performed on tree data structures. It is a way in which nodes in the tree is visited exactly once in a systematic manner.
Types of traversal:
In-order traversal
Preorder traversal
Post-order traversal
Binary Search Tree
A binary search tree is a binary tree which is either empty or satisfies the following rules:
1. The value of the key in the left child or left sub-tree is less than the value of the root.
2. The value of the key in the right child or right sub-tree is more than or equal to the value of the root.

2-3 Tree
This is another type of a height balanced tree. It is a type of a tree where all the non-terminal nodeshave either 2 or 3 children. All the leaf nodes are at the same length from the root node in a similar path. A treeconsisting of a single leaf node is also considered to be a 2-3 tree.

A 2-3tree satisfies the following requirements:
All internal nodes in the tree have either two or three children. All leaves of the tree are at the same level.
Insert Operation:
To insert a new leaf in a 2-3 tree, locate the position where the new leaf should be inserted and add the new leafto the tree. Invoke the parent of the newly inserted leaf and if the number of children has increased from two tothree, no further change is needed. If the number of children of the parent has increased from three to four, splitthe parent into two nodes with two children each, incrementing the number of children. Proceed recursively upto the root of the tree, and, if needed, add a new root to augment the height of the tree by one. In this manner,an insert operation is performed.
Delete Operation
In a delete operation the leaf is located and removed. If the number of children has decreased in the parent node from three to two, the tree is still 2-3. If the number of children of the parent has decreased from two to one, merge it with one of its siblings. Precederecursively up to the root of the tree. Finally, if the root is of degree one, remove it and make its child the root.

Exercise:
1. Create Binary Search tree for the following data:
a , b , t , e , j , o , s , w , q , p , x , k
2. Create AVL tree for the following data:
34 , 67 , 1 , 90 , 37 , 55 , 99 , 22 , 11 , 5 , 78 , 4 , 6 3. Create B tree of order 3 for following:
F G J W Y X Q O P F T X L S C H
4. Create B-tree of order for data given in question no. 3
5. Find the structure of Binary tree when
a. Preorder: a s d f g h j k Inorder: k j h g f d s a b. Postorder: q w e r t y u i o p Inorder : t r e i u o p q w y