Tuesday, July 7, 2020
Latest:
Free text books

# Tree in Data structure

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