161

LESSON 2
TREES

A tree data structure is a powerful tool for organizing data objects based on keys. It is equally useful for
organizing multiple data objects in terms of hierarchical relationships (think of a ``family tree'', where the
children are grouped under their parents in the tree).

Lesson Objectives:
At the end of this lesson, you will be able to:
• Understand Tree in Data Structure and Algorithm.
• Identify Different Trees
• Learn the different algorithm of the trees
• Learn how to plot array elements into binary search tree.
• Understand Tree Traversals

WHAT IS A TREE?

• Tree represents the nodes connected by edges.

• Binary Tree is a special data structure used for data storage purposes.
• A binary tree has the benefits of both an ordered array and a linked list as search is
as quick as in a sorted array and insertion or deletion operation are as fast as in
linked list.

IMPORTANT TERMS
• 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.

Learning Module on PROG 201

 162

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

BINARY SEARCH TREE REPRESENTATION

• Binary Search tree exhibits a special behavior. A node's
left child must have a value less than its parent's value and
the node's right child must have a value greater than its
parent value.

BINARY SEARCH TREE OPERATIONS

• Insert − Inserts an element in a tree/create a tree.

• Search − Searches an element in a tree.
• Preorder Traversal − Traverses a tree in a pre-order manner.
• Inorder Traversal − Traverses a tree in an in-order manner.
• Postorder Traversal − Traverses a tree in a post-order manner

PLOTTING ARRAY ELEMENTS INTO BINARY SEARCH

TREE

Array[]={5,7,1,15,9,2,14,8,7,3 }

ALGORITHM

Step 1.First element is the root node

Step 2.Compare the second element to the root if the second element is
greater than then it will be the right child else it will be place as left
child

Step 3.Continue compare the next element from the array as long as the compared elements is less than to the
node place left if greater that place right

Note: the next node should be place to the leaf node (node that don’t have child)

SEARCH OPERATION Searching Node 25

Learning Module on PROG 201

 163

Learning Module on PROG 201

 164

INSERT OPERATION

INSERT 25 IN Node 25!

Learning Module on PROG 201

 165

DELETE OPERATION

DELETE NODE 11! SINGLE CHILD

BEFORE AFTER

DELETE NODE 24!

TWO CHILDREN

Learning Module on PROG 201

 166

TREE NODE

INSERT OPERATION ALGORITHM

Note: Start searching from the root node, then if the data is less than the key value, search for the empty
location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and
insert the data.

Learning Module on PROG 201

 167

AVL TREE

WHAT IS AVL TREE?

• Adelson, Velski & Landis, AVL trees

• Are height balancing binary search tree. AVL tree checks the height of the left and the right sub-trees
and assures that the difference is not more than 1. This difference is called the Balance Factor.

BalanceFactor = height(left-subtree) − height(right-subtree)

In the second tree, the left subtree of C has height 2 and the right subtree has height 0, so the difference is 2. In
the third tree, the right subtree of A has height 2 and the left is missing, so it is 0, and the difference is 2 again.
AVL tree permits difference (balance factor) to be only 1.

Learning Module on PROG 201

 168

WHAT IS BALANCE?

• For a Tree to be balance ,the value has only be -1,0 or 1

• Balance(tree)=height of the (tree. Left)-height of the (tree.Right)

AVL ROTATIONS
To balance itself, an AVL tree may
perform the following four kinds of
rotations −

• Left rotation
• Right rotation
• Left-Right rotation
• Right-Left rotation

The first two rotations are single rotations and the next two rotations are double rotations. To have an
unbalanced tree, we at least need a tree of height 2. With this simple tree, let's understand them one by one.

Left Rotation
If a tree becomes unbalanced, when a node is
inserted into the right subtree of the right
subtree, then we perform a single left rotation
−
In our example, node A has become
unbalanced as a node is inserted in the right
subtree of A's right subtree. We perform the
left rotation by making A the left-subtree of B.
Right Rotation
AVL tree may become unbalanced, if a node is
inserted in the left subtree of the left subtree. The tree
then needs a right rotation.
As depicted, the unbalanced node becomes the right
child of its left child by performing a right rotation.

Learning Module on PROG 201

 169

SPLAY TREE

• A splay tree is just a binary search tree that has excellent performance in the cases where some data is
accessed more frequently than others. The tree self-adjusts after lookup, insert and delete operations.
• A splay tree does not necessarily have minimum height, nor does it necessarily have logarithmically
bounded height. In fact a splay tree may even be degenerate. However, it is based on the idea that if you
recently used something you'll likely need it again soon, so it keeps the most commonly used data near
the top where it is accessed most quickly.

How it works

After each insert, delete, or lookup,

you splay:

• The node you just looked up, or

• The node you just inserted, or
• The parent of the node you just
deleted

Learning Module on PROG 201

 170

B TREES

B-Tree is a self-balancing search tree. In most of the other self-balancing search trees (like AVL and Red-Black
Trees), it is assumed that everything is in main memory.

Search Operation in B-Tree:

Search is similar to the search in Binary Search Tree. Let the key to be searched be k. We start from the root
and recursively traverse down. For every visited non-leaf node, if the node has the key, we simply return the
node. Otherwise, we recur down to the appropriate child (The child which is just before the first greater key) of
the node. If we reach a leaf node and don’t find k in the leaf node, we return NULL.

Logic:
Searching a B-Tree is similar to searching a binary tree. The algorithm is similar and goes with recursion. At
each level, the search is optimized as if the key value is not present in the range of parent then the key is present
in another branch. As these values limit the search they are also known as limiting value or separation value. If
we reach a leaf node and
don’t find the desired key
then it will display NULL.

Example: Searching 120 in

the given B-Tree.

Learning Module on PROG 201

 171

Note:

In this example, we can see that our search was reduceby just limiting the chances where the key containing the
value could be present. Similarly if within the above example we’ve to look for 180, then the control will stop at
step 2 because the program will find that the key 180 is present within the current node. And similarly, if it’s to
seek out 90 then as 90 < 100 so it'll go to the right subtree automatically and therefore the control flow will go
similarly as shown within the above example.

TREE TRAVERSAL

WHAT IS TRAVERSAL?

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

THREE WAYS WHICH WE USE TO TRAVERSE A TREE

In-Order Traversal

In this traversal method, the left subtree is visited first, then the root and later the right sub-tree. 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 −

Learning Module on PROG 201

 172

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

ALGORITHM
Until all nodes are traversed
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

Pre-Order Traversal

In this traversal method, the root node is visited first, then the left subtree and finally the right subtree

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 root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.

Learning Module on PROG 201

 173

Post-Order Traversal

In this traversal method, the root node is visited last, hence the name. First we traverse the left subtree, then the
right subtree and finally the root node.

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

ALGORITHM
Until all nodes are traversed
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

Learning Module on PROG 201

 174

SUMMARY

• A binary tree has the benefits of both an ordered array and a linked list as search is as quick as in a
sorted array and insertion or deletion operation are as fast as in linked list.
• Path refers to the sequence of nodes along the edges of a tree.
• Root refers to 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 refers to any node except the root node has one edge upward to a node called parent.
• Child refers to the node below a given node connected by its edge downward is called its child node.
• Leaf refers to the node which does not have any child node is called the leaf node.
• Subtree represents the descendants of a node.
• Visiting refers to checking the value of a node when control is on the node.
• Traversing means passing through nodes in a specific order.
• 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.
• Key represents a value of a node based on which a search operation is to be carried out for a node.
• Binary Search tree exhibits a special behavior. A node's left child must have a value less than its parent's
value and the node's right child must have a value greater than its parent value.
• Preorder 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
• Adelson, Velski & Landis, AVL trees
• A splay tree is just a binary search tree that has excellent performance in the cases where some data is
accessed more frequently than others. The tree self-adjusts after lookup, insert and delete operations.
• B-Tree is a self-balancing search tree. In most of the other self-balancing search trees (like AVL and
Red-Black Trees), it is assumed that everything is in main memory.

Learning Module on PROG 201