Tree Data Structure

Tree

A Tree is a recursive data structure containing the set of one or more data nodes where one node is designated as the root of the tree while the remaining nodes are called as the children of the root.

Nodes of a tree either maintain a parent-child relationship. In a general tree, A node can have any number of children nodes but it can have only a single parent.

concept of tree data structure
Binary Tree
Binary Search Tree
Advantages of Binary Search Tree
Representation of Binary search tree
Traversal in Tree

Root Node

The root node is the topmost node in the tree hierarchy. In other words, the root node is the one which doesn't have any parent.

Sub Tree

If the root node is not null, the tree T1, T2 and T3 are called sub-trees of the root node.

Leaf Node

The node of a tree, which doesn't have any child nodes, is called leaf node. Leaf node is the bottom most node of the tree. There can be any number of leaf nodes present in a general tree. Leaf nodes can also be called external nodes.

Path

The sequence of consecutive edges is called path. In the tree shown in the above image, the path to the node E is A→ B → E.

Ancestor node

An ancestor of a node is any predecessor node on a path from root to that node. The root node doesn't have any ancestors. In the tree shown in the above image, the node F have the ancestors, B and A.

Degree

Degree of a node is equal to number of children a node has. In the tree shown in the above image, the degree of node B is 2. Degree of a leaf node is always 0 while in a complete binary tree, degree of each node is equal to 2.

Level Number

Each node of the tree is assigned a level number in such a way that each node is present at one level higher than its parent. Root node of the tree is always present at level 0.

Path

Path refers to the sequence of nodes along the edges of a tree.

Root

The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node. Parent − Any node except the root node has one edge upward to a node called parent.

Child

The node below a given node connected by its edge downward is called its child node.

Leaf

The node which does not have any child node is called the leaf node. Subtree − Subtree represents the descendants of a node.

Visiting

Visiting refers to checking the value of a node when control is on the node.

Traversing

Traversing means passing through nodes in a specific order.

Levels − Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.

keys − Key represents a value of a node based on which a search operation is to be carried out for a node.

Tree

It is a non linear data Structure. It has hierarchical structure Tree grows from top to bottom. It follows a particular direction. Tree can be defined as a collection of nodes which are linked together to simulate a hierarchy.

Depth of node

Length of the path from root to that node is called depth. Height of the node:- Number of edges in the longest path from that node to leaf node.

General node

General Tree stores the elements in a hierarchical order in which the top level element is always present at level 0 as the root element. All the nodes except the root node are present at number of levels.

The nodes which are present on the same level are called siblings while the nodes which are present on the different levels exhibit the parent-child relationship among them. A node may contain any number of sub-trees. The tree in which each node contain 3 sub-tree, is called ternary tree. No restrictions on General Tree.

Forest

Forest can be defined as the set of disjoint trees which can be obtained by deleting the root node and the edges which connects root node to the first level node.

Binary tree

Binary tree is a data structure in which each node can have at most 2 children. The node present at the top most level is called the root node. A node with 0 children is called leaf node. Binary Trees are used in applications like expression evaluation and many more.

Binary search tree

Binary search tree is an ordered binary tree. All the elements in the left subtree are less than the root while elements present in the right subtree are greater than or equal to the root node element.

Binary search trees are used in most of the applications of computer science domain like searching, sorting, etc.

Expression tree

Expression trees are used to evaluate the simple arithmetic expressions.

Expression tree is basically a binary tree where internal nodes are represented by operators while leaf nodes are represented by operands.

Expression trees are widely used to solve algebraic expressions like (a+b)*(a-b).

Types of Binary tree

Strictly Binary Tree

In the Strictly Binary Tree, every non-leaf node contains non-empty left and right subtrees. In other words, the degree of every non-leaf node will always be 2. No of leaf nodes=No of internal nodes+1

Complete Binary tree

A Binary Tree is said to be a complete binary tree if all of the leaves are located at the same level d. A complete binary tree is a binary tree that contains exactly 2^l nodes at each level between level 0 and d.

Perfect Binary tree

A Binary tree is a Perfect Binary Tree in which all the internal nodes have two children and all leaf nodes are at the same level.

Skewed Binary tree

A skewed binary tree is a type of binary tree in which all the nodes have only either one child Types of Skewed Binary trees There are 2 special types of skewed tree: or no child.

Left Skewed Binary Tree

These are those skewed binary trees in which all the nodes are having a left child or no child at all. It is a left side dominated tree. All the right children remain as null.

Right Skewed Binary Tree

These are those skewed binary trees in which all the nodes are having a right child or no child at all. It is a right side dominated tree. All the left children remain as null.

Binary tree presentation

There are two types of representation of a binary tree:

Linked Representation

In this representation, the binary tree is stored in the memory, in the form of a linked list where the number of nodes are stored at non-contiguous memory locations and linked together by inheriting parent-child relationship like a tree. every node contains three parts : pointer to the left node, data element and pointer to the right node. Each binary tree has a root pointer which points to the root node of the binary tree. In an empty binary tree, the root pointer will point to null.

A tree is seen as the collection of nodes where each node contains three parts : left pointer, data element and right pointer. Left pointer stores the address of the left child while the right pointer stores the address of the right child. The leaf node contains null in its left and right pointers.

The following image shows how the memory will be allocated for the binary tree by using linked representation. There is a special pointer maintained in the memory which points to the root node of the tree. Every node in the tree contains the address of its left and right child. Leaf node contains null in its left and right pointer.

Binary search tree

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties − The value of the key of the left sub-tree is less than the value of its parent (root) node's key.

The value of the key of the right subtree is greater than or equal to the value of its parent (root) node's key. Thus, BST divides all its sub-trees into two segments; the left subtree and the right subtree and can be defined as − left_subtree (keys) < node (key) ≤ right_subtree (keys)

Binary Search tree can be defined as a class of binary trees, in which the nodes are arranged in a specific order. This is also called an ordered binary tree.

In a binary search tree, the value of all the nodes in the left sub-tree is less than the value of the root. Similarly, the value of all the nodes in the right subtree is greater than or equal to the value of the root.

This rule will be recursively applied to all the left and right subtrees of the root.

Advantages of Binary search tree

Searching becomes very efficient in a binary search tree.
The binary search tree is considered as an efficient data structure in comparison to arrays and linked lists. In the searching process, it removes half a sub-tree at every step.
It also speeds up the insertion and deletion operations as compared to that in array and linked list.

Representation of Binary search tree

BST is a collection of nodes arranged in a way where they maintain BST properties. Each node has a key and an associated value. While searching, the desired key is compared to the keys in BST and if found, the associated value is retrieved.

Basic operation

Following are the basic operations of a tree

Search − Searches an element in a tree.
Insert − Inserts an element in a tree.
Pre-order Traversal − Traverses a tree in a pre-order manner.
In-order Traversal − Traverses a tree in an in-order manner.
Post-order Traversal − Traverses a tree in a post-order manner.

Common operation of trees

Searching for one item(traversal)
Adding the new item
Deleting the item
Removing a whole selection of a tree(pruning)
Adding a whole section to a tree.(grafting)
Finding the root of any node.

Define a node having some data references to its left and right child nodes.

struct node

 { int data; 

    struct node *leftChild; 

       struct node *rightChild; 

       };

A binary tree can be represented using

Static representation
Dynamic representation

Search operation on binary tree Whenever an element is to be searched, start searching from the root node. Then if the data is less than the key value, search for the element in the left subtree. Otherwise, search for the element in the right subtree. Follow the same algorithm for each node.

In a binary search tree, the search operation is performed with O(log n) time complexity. The search operation is performed as follows…

Step 1 - Read the search element from the user.
Step 2 - Compare the search element with the value of the root node in the tree.
Step 3 - If both are matched, then display "Given node is found!!!" and terminate the function.
Step 4 - If both are not matched, then check whether the search element is smaller or larger than that node value.
Step 5 - If the search element is smaller, then continue the search process in the left subtree.
Step 6- If the search element is larger, then continue the search process in the right subtree.
Step 7 - Repeat the same until we find the exact element or until the search element is compared with the leaf node.
Step 8 - If we reach the node having the value equal to the search value then display "Element is found" and terminate the function.
Step 9 - If we reach the leaf node and if it is also not matched with the search element, then display "Element is not found" and terminate the function.

Searching means finding or locating some specific element or node within a data structure. However, searching for some specific node in a binary search tree is pretty easy due to the fact that elements in BST are stored in a particular order.

Compare the element with the root of the tree.
If the item is matched then return the location of the node.
Otherwise check if the item is less than the element present on the root, if so then move to the left sub-tree.
If not, then move to the right subtree. Repeat this procedure recursively until a match is found.
If an element is not found then return NULL.

Algorithm

Search (ROOT, ITEM)
IF ROOT -> DATA = ITEM OR ROOT = NULL Return ROOT
ELSE IF ROOT < ROOT -> DATA Return search(ROOT -> LEFT, ITEM)
ELSE Return search(ROOT ->RIGHT,ITEM)
[END OF IF] [END OF IF] END

Insertion operation in Binary search tree

Insert function is used to add a new element in a binary search tree at appropriate location. Insert function is to be designed in such a way that it must violate the property of binary search tree at each value.

Allocate the memory for trees.
Set the data part to the value and set the left and right pointer of the tree, pointing to NULL.
If the item to be inserted, will be the first element of the tree, then the left and right of this node will point to NULL.
Else, check if the item is less than the root element of the tree, if this is true, then recursively perform this operation with the left of the root.
If this is false, then perform this operation recursively with the right subtree of the root.

Insert (TREE, ITEM) Step 1: IF TREE = NULL Allocate memory for TREE SET TREE -> DATA = ITEM SET TREE -> LEFT = TREE ->RIGHT = NULL ELSE IF ITEM < TREE -> DATA Insert(TREE -> LEFT, ITEM) ELSE Insert(TREE -> RIGHT, ITEM) [END OF IF] [END OF IF]
Step 2: END

Delete Operation on Binary tree

Delete function is used to delete the specified node from a binary search tree. However, we must delete a node from a binary search tree in such a way that the property of the binary search tree doesn't violate. There are three situations of deleting a node from a binary search tree.

Algorithm for deleting leaf

Delete (TREE, ITEM) Step 1: IF TREE = NULL Write "item not found in the tree" ELSE IF ITEM < TREE -> DATA Delete(TREE->LEFT, ITEM) ELSE IF ITEM > TREE -> DATA Delete(TREE -> RIGHT, ITEM) ELSE IF TREE -> LEFT AND TREE -> RIGHT SET TEMP = findLargestNode(TREE -> LEFT) SET TREE -> DATA = TEMP -> DATA Delete(TREE -> LEFT, TEMP -> DATA) ELSE SET TEMP = TREE IF TREE -> LEFT = NULL AND TREE -> RIGHT = NULL SET TREE = NULL ELSE IF TREE -> LEFT != NULL SET TREE = TREE -> LEFT ELSE SET TREE = TREE ->RIGHT [END OF IF] FREE TEMP [END OF IF]
Step 2: END

Traversal in Tree

Traversal is a process to visit all the nodes of a tree and may print their values too. Because all nodes are connected via edges (links) we always start from the root (head) node. That is, we cannot randomly access a node in a tree. There are three ways which we use to traverse a tree −

In-order Traversal
Pre-order Traversal
Post-order Traversal

In order traversal

In this traversal method, the left subtree is visited first, then the root and later the right subtree. We should always remember that every node may represent a subtree itself.

If a binary tree is traversed in-order, the output will produce sorted key values in an ascending order.

We start from A, and following in-order traversal, we move to its left subtree B. B is also traversed in-order. The process goes on until all the nodes are visited. The output of inorder traversal of this tree will be − D → B → E → A → F → C → G

Algorithm

Until all nodes are traversed −

Step 1 − Recursively traverse left subtree.
Step 2 − Visit the root node.
Step 3 − Recursively traverse the right subtree.

Pre order traversal

We start from A, and following pre-order traversal, we first visit A itself and then move to its left subtree B. B is also traversed pre-order. The process goes on until all the nodes are visited. The output of pre-order traversal of this tree will be − A → B → D → E → C → F → G

Algorithm

Until all nodes are traversed −

Step 1 − Visit the root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse the right subtree.

Post order traversal

We start from A, and following Post-order traversal, we first visit the left subtree B. B is also traversed post-order. The process goes on until all the nodes are visited. The output of post-order traversal of this tree will be − D → E → B → F → G → C → A

Until all nodes are traversed −

Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse the right subtree.
Step 3 − Visit the root node.