**Introduction to Trees [Data Structure]**

**——————————————————-**

**A tree is a finite set of one or more nodes**

**There is a specially designated node called the root **

**Remaining nodes are partitioned into n>=0 disjoint sets T1,…..Tn, where each of these sets is a tree.**

**The sets T1,…. Tn are called subtrees of the root.**

**Terminologies in Tree**

**———————————-**

**The degree of a node is defined as the number of subtrees of that node.**

**Nodes that have degree zero are called leaf or terminal nodes.**

**The other nodes are referred to as non-terminals.**

**The nodes, which are subtrees of some other node, are called children of that node.**

**The node, which contains subtrees, are called the parent.**

**Children of the same parent are said to be siblings.**

**The degree of a tree is the maximum of degree of the nodes of the tree.**

**The level of a node is defined by initially letting the root be at level one.**

**The height or depth of a tree is defined to be the maximum level of any node in that tree.**

**Application of Trees**

**——————————-**

**Trees can be implemented in following applications**

**Implementing the file systems of several operating systems.**

**Evaluation of Arithmetic expressions.**

**Set Representations.**

**Efficient sorting.**

**Reduction of the time complexity of some searching operations.**

**Operations and traversal on trees**

**—————————————————-**

**Basically, binary tree traversal can be carried out in 3 ways.**

**Inorder****Preorder****Postorder**

**Inorder: In this method of traversal, first the left sub tree is traversed (visited), then the root and finally traversing the right sub tree.**

**Preorder: In this method, the root is traversed first, then the left sub tree and finally visiting the right sub tree.**

**Postorder:In this method, left sub tree is traversed first, then right sub tree and finally visiting the root.**

**Binary Trees**

**————————–**

**A binary tree is a finite set of nodes that is either empty or consists of a root and two disjoint binary trees called the left and right subtrees.**

**Types of Binary Trees**

**————————————-**

**There are two special kinds of binary trees.**

**Skewed tree****Complete Binary tree.**

**Binary Search Trees**

**————————————–**

**A Binary Search Tree is a binary tree. It may be empty. If it is not empty, then it satisfies the following properties.**

**Every element has a key and no two elements have the same key (i.e., the keys are distinct).**

**The keys (if any) in the left sub tree are smaller than the key in the root.**

**The keys (if any) in the right sub tree are greater than the key in the root.**

**The left and right sub trees are also binary search trees.**

**Operations on Binary Search Tree**

**————————————————**

**Searching a Binary Search Tree**

**Insertion Into a Binary Search Tree**

**Deletion from a Binary Search Tree**