BINARY TREES

In data structures, a tree is a hierarchical data structure composed of nodes connected by edges,
forming a parent-child relationship.

Terminologies used in trees

 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. In the above structure, node numbered 1 is the root
node of the tree.

 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 atleast one child node known as an internal node

 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. In the tree shown in the above image,
nodes 1, 2, and 5 are the ancestors of node 10.

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

node. In the above figure, 10 is the descendant of node 5.

TYPES OF TREE DATA STRUCTURES

1. General tree: The general tree is one of the types of tree data structure. In the general
tree, a node can have either 0 or maximum n number of nodes. There is no restriction
imposed on the degree of the node.

2. Binary tree: Here, binary name itself suggests two numbers, i.e., 0 and 1. In a binary
tree, each node in a tree can have utmost two child nodes. Here, utmost means whether
the node has 0 nodes, 1 node or 2 nodes.

3. Binary search tree: Binary search tree is a non-linear data structure in which one node is
connected to n number of nodes. It is a node-based data structure. A node can be
represented in a binary search tree with three fields, i.e., data part, left-child, and right-
child. A node can be connected to the utmost two child nodes in a binary search tree, so
the node contains two pointers (left child and right child pointer). Every node in the left
subtree must contain a value less than the value of the root node, and the value of each
node in the right subtree must be bigger than the value of the root node.

4. AVL TREES : AVL tree satisfies the property of the binary tree as well as of the binary
search tree. Here, self-balancing means that balancing the heights of left subtree and
right subtree. This balancing is measured in terms of the balancing factor.
The balancing factor can be defined as the difference between the height of the left subtree and the
height of the right subtree. The balancing factor's value must be either 0, -1, or 1; therefore, each
node in the AVL tree should have the value of the balancing factor either as 0, -1, or 1.

5. RED BLACK TREE

The red-Black tree is the binary search tree. The prerequisite of the Red-Black tree is that we should
know about the binary search tree. In a binary search tree, the value of the leftsubtree should be less
than the value of that node, and the value of the right-subtree should be greater than the value of
that node. As we know that the time complexity of binary search in the average case is log2n, the
best case is O(1), and the worst case is O(n).

6. B-TREE :

B-tree is a balanced m-way tree where m defines the order of the tree. Till now, we read that the
node contains only one key but b-tree can have more than one key, and more than 2 children. It
always maintains the sorted data. In binary tree, it is possible that leaf nodes can be at different
levels, but in b-tree, all the leaf nodes must be at the same level. If order is m then node has the
following properties: o Each node in a b-tree can have maximum m children o For minimum children,
a leaf node has 0 children, root node has minimum 2 children and internal node has minimum ceiling
of m/2 children. For example, the value of m is 5 which means that a node can have 5 children and
internal nodes can contain maximum 3 children. o Each node has maximum (m-1) keys. The root
node must contain minimum 1 key and all other nodes must contain atleast ceiling of m/2 minus 1
keys.

BINARY TREES:

The Binary tree means that the node can have maximum two children. Here, binary name itself
suggests that 'two'; therefore, each node can have either 0, 1 or 2 children.

Types of Binary Tree

There are four types of Binary tree:

 Full/ proper/ strict Binary tree

 Complete Binary tree

 Perfect Binary tree

 Degenerate Binary tree

 Balanced Binary tree

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

2. Complete Binary Tree

The complete binary tree is a tree in which all the nodes are completely filled except the last level. In
the last level, all the nodes must be as left as possible. In a complete binary tree, the nodes should be
added from the left.

3. 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.
 4. Balanced Binary Tree

The balanced binary tree is a tree in which both the left and right trees differ by atmost 1. For
example, AVL and Red-Black trees are balanced binary tree.

BINARY TREE TRAVERSAL

There are three traversal methods in BST

a. Inorder

b. Pre-order

c. Post-order

a. INORDER

In this traversal method, the left subtree is visited first, then the root and later the right sub-tree.

Left->root->right

DBEAFCG
Algorithm inorder

Step 1 : [check for empty tree]

if root ==NULL then,

Write “tree is empty”

Step 2:[traverse the left subtree]

If left[root]!=NULL

Call inorder(left[root])

Step 3 : [process the root node]

Process info[root]

Step 4 : [traverse the right subtree]

If right[root]!= NULL

Call inorder(right[root])

Step 5 : return

b. PREORDER

pre-order Traversal : In this traversal method, the root node is visited first, then the left subtree and
finally the right subtree.

Root->Left->right
 A→B→D→E→C→F→G

ALGORITHM INORDER

Step 1 : [process the root node]

if root != NULL then,

Process info[root]

else

Write “tree is empty”

Step 2:[traverse the left subtree]

If left[root]!=NULL

Call preorder(left[root])

Step 3 : [traverse the right sub tree]

If right[root]!= null

Call preorder(right[root])

Step 4 : return

c. POSTORDER
In this traversal method, we traverse the left subtree, then the right subtree and finally the root
node.

Left->right->root

D→E→B→F→G→C→A

ALGORITHM

Step 1 : [check for empty tree]

if root ==NULL then,

Write “tree is empty”

Step 2:[traverse the left subtree]

If left[root]!=NULL

Call postorder(left[root])

Step 3 : [traverse the right subtree]

If right[root]!= NULL

Call postorder(right[root])

Step 4 : [process the root node]

Process info[root]

Step 5 : return
 BINARY SEARCH TREE

A Binary Search Tree (BST) is a tree-like data structure that organizes data in tree like data structure
to store and search data. In BST , the key value of the left child is always less than the key value of its
parent node and the key value of the right child is always equal to or greater than the key value of its
parent node.

Advantages of using binary search tree

1. Searching become very efficient in a binary search tree since, we get a hint at each step, about
which sub-tree contains the desired element.

2. The binary search tree is considered as efficient data structure in compare to arrays and linked
lists. In searching process, it removes half sub-tree at every step. Searching for an element in a binary
search tree takes o(log2n) time. In worst case, the time it takes to search an element is 0(n).

3. It also speed up the insertion and deletion operations as compare to that in array and linked list.

Q. Create the binary search tree using the following data elements. 43, 10, 79, 90, 12, 54, 11, 9, 50
BINARY SEARCH TREE OPERATIONS
ALGORITHM TO INSERT AN NODE IN BST

• Step 1 : create a new node

• Dynamically allocate memory using getnode() to a new node.

• Store the value to be inserted into the field of the new node

• Step 2: Assign the root nodes address to two pointers CURRPTR->used to find location of
new node and PTR-> to keep track of parent node.

• Step 3 : Traverse the tree

• Compare the value if its less move to the left subtree and if its greater move to the right
subtree.

• Step 4 : Locate the insertion point :

• Step 5: insert the new node.

ALGORITHM : SEARCH IN BST

• Step 1: check if the tree is empty if the temp is NULL and is true than item is not found.

• Step 2: compare the item with the current node

• If the value of item is less than info[temp],move to the left subtree

• Else move to the right tree

• Step 3: check for a match

• If the value of the item is equal to the info[temp],the search is successful.

• Step 4: repeat : continue the process until the item is found.

DELETE IN BST

• One of the hardest operation in binary trees as well as BST, cases to consider

• Case 1: Node N is the leaf node

• Identify the node to be deleted and remove it directly

• Case 2: Node N has a exactly one child

• Find the Node: Similar to the leaf case, locate the node to be deleted.

• Replace with Child: Replace the node with its only child. If the node has a left child, make the
parent point to the left child. If it has a right child, make the parent point to the right child.
ALGORITHM : DELETING IN BST

Step 1 : search for the node

Start with root node search for the node which is to be deleted.

Step 2 : check the cases of the node

If the node is a leaf node delete it directly

If the node to be deleted has only one child then the child replaces the deleted node

If node has two children find the inorder successor of the node to be deleted.

AVL TREES

AVL Tree can be defined as height balanced binary search tree in which each node is associated with
a balance factor which is calculated by subtracting the height of its right subtree from that of its left
sub-tree.

Tree is said to be balanced if balance factor of each node is in between -1 to 1, otherwise, the tree
will be unbalanced and need to be balanced.

Balance Factor (k) = height (left(k)) - height (right(k))

If balance factor of any node is 1, it means that the left sub-tree is one level higher than the right
sub-tree.

If balance factor of any node is 0, it means that the left sub-tree and right sub-tree contain equal
height.

If balance factor of any node is -1, it means that the left sub-tree is one level lower than the right
sub-tree.
AVL rotations

• There are basically four types of rotations which are as follows:

• 1. L L rotation: Inserted node is in the left subtree of left subtree of A

• 2. R R rotation : Inserted node is in the right subtree of right subtree of A

• 3. L R rotation : Inserted node is in the right subtree of left subtree of A

• 4. R L rotation : Inserted node is in the left subtree of right subtree of A

• The first two rotations LL and RR are single rotations and the next two rotations LR and RL
are double rotations.

1. RR Rotations: When BST becomes unbalanced, due to a node is inserted into the right
subtree of the right subtree of A, then we perform RR rotation, RR rotation is an
anticlockwise rotation, which is applied on the edge below a node having balance factor
-2.
2. LL Rotations : When BST becomes unbalanced, due to a node is inserted into the left subtree of
the left subtree of C, then we perform LL rotation, LL rotation is clockwise rotation, which is applied
on the edge below a node having balance factor 2.

• 3. LR Rotation : LR rotation = RR rotation + LL rotation, i.e., first RR rotation is performed on

subtree and then LLrotation is performed on full tree, by full tree we mean the first node
from the path of inserted node whose balance factor is other than -1, 0, or 1.

• 4. RL Rotation : R L rotation = LL rotation + RR rotation, i.e., first LL rotation is performed on

subtree and then RR rotation is performed on full tree, by full tree we mean the first node
from the path of inserted node whose balance factor is other than -1, 0, or 1.
B-TREES

B Tree is a specialized m-way tree that can be widely used for disk access. A B-Tree of order m can
have at most m-1 keys and m children. One of the main reason of using B tree is its capability to store
large number of keys in a single node and large key values by keeping the height of the tree relatively
small.

A B tree of order m contains all the properties of an M way tree. In addition, it contains the following
properties.

1. Every node in a B-Tree contains at most m children.

2. Every node in a B-Tree except the root node and the leaf node contain at least m/2 children.

3. The root nodes must have at least 2 nodes.

4. All leaf nodes must be at the same level. It is not necessary that, all the nodes contain the same
number of children but, each node must have m/2 number of nodes. A B tree of order 4 is shown in
the following image.

Insertion in B+ Tree
Step 1: Insert the new node as a leaf node

Step 2: If the leaf doesn't have required space, split the node and copy the middle node to the next
index node.

Step 3: If the index node doesn't have required space, split the node and copy the middle element
to the next index page.
Deletion in B+ Tree

Step 1: Delete the key and data from the leaves.

Step 2: if the leaf node contains less than minimum number of elements, merge down the node with
its sibling and delete the key in between them.

Step 3: if the index node contains less than minimum number of elements, merge the node with the
sibling and move down the key in between them.

Example Delete the key 200 from the B+ Tree shown in the following figure.
Heap

A heap is a tree-based data structure that forms a complete binary tree, and satisfies the heap
property. If A is a parent node of B, then A is ordered with respect to the node B for all nodes A and B
in a heap. It means that the value of the parent node could be more than or equal to the value of the
child node, or the value of the parent node could be less than or equal to the value of the child node.
Therefore, we can say that there are two types of heaps:

Max heap: The max heap is a heap in which the value of the parent node is greater than the value of
the child nodes.

Min heap: The min heap is a heap in which the value of the parent node is less than the value of the
child nodes.