Trees

A tree is recursively defined as a set of one or more nodes where one node is designated as the root of the tree and all the remaining nodes can be partitioned into non empty sets each of which is a sub tree of the root.

A tree is also one of the data structures that represent hierarchical data.

Tree Data structure Glossary

• Root: The root node is the topmost node in the tree hierarchy. In other words, the root node is the one that doesn’t have any parent. If a node is directly linked to some other node, it would be called a parent-child relationship.

• Child node: If the node is a descendant of any node, then the node is known as a child node.

• Parent: If the node contains any sub-node, then that node is said to be the parent of that sub-node.

• Sibling: The nodes that have the same parent are known as siblings.

• Leaf Node:- The node of the tree, which doesn’t have any child node, is called a leaf node. A 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.

• Internal nodes: A node has at least one child node known as an internal

• Ancestor node:- An ancestor of a node is any predecessor node on a path from the root to that node. The root node doesn’t have any ancestors.

• Descendant: The immediate successor of the given node is known as a descendant of a node.

Tree Traversals

The process of visiting the nodes is known as tree traversal. There are three types traversals used to visit a node:

• In-order traversal: In this traversal method, the left sub-tree is visited first, then the root and later the right sub-tree. We should always remember that every node may represent a sub-tree itself.

• Pre-order traversal: In this traversal method, the root node is visited first, then the left sub-tree and finally the right sub-tree.

• Post-order traversal: In this traversal method, the root node is visited last, hence the name. First we traverse the left sub-tree, then the right sub-tree and finally the root node.

Binary Tree

A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.

A binary tree contains data, left child and a right child

Properties of Binary Tree

· At each level of i, the maximum number of nodes is 2i.

· The height of the tree is defined as the longest path from the root node to the leaf node.

· The minimum number of nodes possible at height h is equal to h+1.

· If the number of nodes is minimum, then the height of the tree would be maximum. Conversely, if the number of nodes is maximum, then the height of the tree would be minimum.

Types of Binary Tree

• Full/ proper/ strict Binary tree: The full binary tree is also known as a strict binary tree. The tree can only be considered as the full binary tree if each node must contain either 0 or 2 children. The full binary tree can also be defined as the tree in which each node must contain 2 children except the leaf nodes.

• Complete Binary tree: The complete binary tree is a tree in which all the nodes are completely filled except the last level.

• Perfect Binary tree: A tree is a perfect binary tree if all the internal nodes have 2 children, and all the leaf nodes are at the same level.All the perfect binary trees are the complete binary trees as well as the full binary tree, but vice versa is not true, i.e., all complete binary trees and full binary trees are the perfect binary trees.

• Degenerate Binary tree: A tree in which all the internal nodes have only one children.It is known as a right-skewed tree if all the nodes have a right child only and known as a left-skewed tree if all the nodes have a left child only.

Right-skewed tree

Left-skewed tree

• Balanced Binary tree: The balanced binary tree is a tree in which both the left tree and right tree differ by at most 1.

Binary Tree Node Implementation

A Binary tree is implemented with the help of pointers. The first node in the tree is represented by the root pointer. Each node in the tree consists of three parts, i.e., data, left pointer and right pointer. To create a binary tree, we first need to create the node. We will create the node of user-defined as shown below:

struct node {
    int data;
    struct node *left, *right;
}

In the above structure, data is the value, left pointer contains the address of the left node, and right pointer contains the address of the right node.

Binary Search Tree

Binary Search Tree is a node-based binary tree data structure which has the following properties:

· The left sub-tree of a node contains only nodes with keys lesser than the node’s key.

· The right sub-tree of a node contains only nodes with keys greater than the node’s key.

· The left and right sub-tree each must also be a binary search tree.

Searching in Binary Search Tree

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

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

Algorithm:

Insertion 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 node violate the property of binary search tree at each value.

1. Allocate the memory for tree.
2. Set the data part to the value and set the left and right pointer of tree, point to NULL.
3. 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.
4. 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.
5. If this is false, then perform this operation recursively with the right sub-tree of the root.

Algorithm:

Deletion in Binary search 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 binary search tree doesn’t violate. There are three situations of deleting a node from binary search tree.

The node to be deleted is a leaf node: It is the simplest case, in this case, replace the leaf node with the NULL and simply free the allocated space.

The node to be deleted has only one child: In this case, replace the node with its child and delete the child node, which now contains the value which is to be deleted. Simply replace it with the NULL and free the allocated space.

The node to be deleted has two children: It is a bit complicated case compare to other two cases. However, the node which is to be deleted, is replaced with its in-order successor or predecessor recursively until the node value (to be deleted) is placed on the leaf of the tree. After the procedure, replace the node with NULL and free the allocated space.

Algorithm:

Time complexity of Binary search tree:

B Tree

B Tree is a self-balancing data structure based on a specific set of rules for searching, inserting, and deleting the data in a faster and memory efficient way. In 1972, this method was first introduced by McCreight, and Bayer named it Height Balanced m-way Search Tree. It helps you to preserves data sorted and allowed various operations like Insertion, searching, and deletion in less time. In order to achieve this, the following rules are followed to create a B Tree.

Properties of B-Tree:

1. All leaves are at the same level.

2. A B-Tree is defined by the term minimum degree ‘t’. The value of t depends upon disk block size.

3. Every node except root must contain at least (ceiling)([t-1]/2) keys. The root may contain minimum 1 key.

4. All nodes (including root) may contain at most t — 1 keys.

5. Number of children of a node is equal to the number of keys in it plus 1.

6. All keys of a node are sorted in increasing order. The child between two keys k1 and k2 contains all keys in the range from k1 and k2.

7. B-Tree grows and shrinks from the root which is unlike Binary Search Tree. Binary Search Trees grow downward and also shrink from downward.

8. Like other balanced Binary Search Trees, time complexity to search, insert and delete is O(log n).

9. Insertion of a Node in B-Tree happens only at Leaf Node.

Search Operation in B tree

The search operation is the simplest operation on B Tree.

The following algorithm is applied:

• Let the key (the value) to be searched by “k”.
• Start searching from the root and recursively traverse down.
• If k is lesser than the root value, search left sub-tree, if k is greater than the root value, search the right sub-tree.
• If the node has the found k, simply return the node.
• If the k is not found in the node, traverse down to the child with a greater key.
• If k is not found in the tree, we return NULL.

Insertion Operation in B tree

Since B Tree is a self-balancing tree, you cannot force insert a key into just any node.

The following algorithm applies:

• Run the search operation and find the appropriate place of insertion.
• Insert the new key at the proper location, but if the node has a maximum number of keys already. The node, along with a newly inserted key, will split from the middle element.
• The middle element will become the parent for the other two child nodes.
• The nodes must re-arrange keys in ascending order.

Deletion Operation in B tree

The delete operation has more rules than insert and search operations.

The following algorithm applies:

• Run the search operation and find the target key in the nodes
• Three conditions applied based on the location of the target key, as explained in the following sections

If the target key is in the leaf node:

• Target is in the leaf node, more than min keys: Deleting this will not violate the property of B Tree
• Target is in leaf node, it has min key nodes: Deleting this will violate the property of B Tree. Target node can borrow key from immediate left node, or immediate right node (sibling). The sibling will say yes if it has more than minimum number of keys. The key will be borrowed from the parent node, the max value will be transferred to a parent, the max value of the parent node will be transferred to the target node, and remove the target value
• Target is in the leaf node, but no siblings have more than min number of keys: Search for key, Merge with siblings and the minimum of parent nodes. Total keys will be now more than min. The target key will be replaced with the minimum of a parent node

If the target key is in an internal node:

• Either choose, in- order predecessor or in-order successor
• In case the of in-order predecessor, the maximum key from its left sub-tree will be selected
• In case of in-order successor, the minimum key from its right sub-tree will be selected
• If the target key’s in-order predecessor has more than the min keys, only then it can replace the target key with the max of the in-order predecessor
• If the target key’s in-order predecessor does not have more than min keys, look for in-order successor’s minimum key.
• If the target key’s in-order predecessor and successor both have less than min keys, then merge the predecessor and successor.

If the target key is in a root node:

• Replace with the maximum element of the in-order predecessor sub-tree
• If, after deletion, the target has less than min keys, then the target node will borrow max value from its sibling via sibling’s parent.
• The max value of the parent will be taken by a target, but with the nodes of the max value of the sibling.

Time complexity of B tree: