**TREE : **A tree is a non linear data structure . Each object of a tree starts with a trunk or root and extends into several branches . Each branch may extend into other branches until finally terminated by a leaf .

**Examples of Tree : **

- Tree can be viewed as lineage of a person that is referred to as the family tree .
- Organizational chart of a company .

In computer applications , a tree is an hierarchical collection of finite elements . Each element is called a node .

**Terms related to tree structure **

**Root Node :**The unique node in the tree that has no parent node is called the root node or root of the tree . It represents the beginning of the tree .**Parent Node :**The node, which generates links for other nodes , is known as the parent node . The parent node is always above its child nodes .**Child Node :**The node that is directly connected to a parent node is called the child node .**Subtree :**The child node of the root node that has its own child nodes is called the subtree .**Terminal Nodes :**The node having no successor or cjild is called the terminal node .**Siblings:**The nodes having a common parent are called siblings . These are children of the same parent node .**Depth of Node:**Each node has a unique path connecting it to the root . The depth of a node is the total number of nodes between the node and the root , including the root itself . The depth of root node is 0 .**Hieght of tree :**The maximum depth among all of the nodes of a tree is called the height of tree .**Empty Tree :**A tree that has no node is called empty Tree . Its height is -1 .**Degree of Node :**The number of children of a node is called degree of the node .

**Types of Tree : **

**Singleton Tree :**The tree whose root us its only node is called the singleton .**Full Tree :**A tree is called the full tree if all its internal nodes have the same degree and all the leaves are at the same level .**Binary Tree :**A binary tree is a hierarchical collection of a finite number of nodes in which each node can have a maximum of two children . A binary tree may be empty or non empty but a general tree cannot be empty . One child is on theleft side and other is on the right side of the tree or subtree .**Full binary tree :**A binary tree is said to be full binary tree when**1.**Its all leaves are at same level .**2.**Every node has two children I.e left child and right child .**Extended Binary Tree (2_Tree) :**A binary tree in which each node has either no child or two children is called an extended binary tree .**Complete Binary Tree:**A binary tree is said to be a complete binary tree of height H if- All nodes at level H_2 and above have two children each .
- A node at level H_1 has one child , it is a left child and all left siblings of the node have two children each .

**Binary Search Tree :**A binary tree in which the left child node of a tree or subtree has lesser value than its root node but right child node has greater (or equal) value than its root node is called binary search tree (BST) .