Unit 4
Unit 4
Unit 4
STRUCTURES - TREES
In a tree data structure, the first node is called as Root Node. Every tree must have a root node. We can
say that the root node is the origin of the tree data structure. In any tree, there must be only one root
node. We never have multiple root nodes in a tree.
EDGE:
PARENT:
LEAF:
Degree of Tree:
HEIGHT:
PATH:
In a tree data structure, each child from a node forms a subtree recursively. Every child node
will form a subtree on its parent node.
Tree Representations
A tree data structure can be represented in two methods. Those methods are as follows...
1.List Representation
2.Left Child - Right Sibling Representation
Consider the following tree...
List Representation
In this representation, we use two types of nodes one for representing the node with data called 'data node'
and another for representing only references called 'reference node'. We start with a 'data node' from the
root node in the tree. Then it is linked to an internal node through a 'reference node' which is further
linked to any other node directly. This process repeats for all the nodes in the tree.
The above example tree can be represented using List representation as follows...
Left Child - Right Sibling Representation
In this representation, we use a list with one type of node which consists of three fields namely Data field, Left child
reference field and Right sibling reference field. Data field stores the actual value of a node, left reference field stores
the address of the left child and right reference field stores the address of the right sibling node. Graphical
representation of that node is as follows...
In this representation, every node's data field stores the actual value of that node. If that node has left a child, then left
reference field stores the address of that left child node otherwise stores NULL. If that node has the right sibling, then
right reference field stores the address of right sibling node otherwise stores NULL.
The above example tree can be represented using Left Child - Right Sibling representation as follows...
Binary Tree Datastructure
A binary tree in which every node has either two or zero number of
children is called Strictly Binary Tree
Strictly binary tree is also called
Strictly binary tree data structure is used to represent
as Full Binary Tree or Proper
mathematical expressions.
Binary Tree or 2-Tree
Complete Binary Tree- Perfect Binary Tree
In a binary tree, every node can have a maximum of two
children. But in strictly binary tree, every node should have
exactly two children or none and in complete binary tree all the
nodes must have exactly two children and at every level of
complete binary tree there must be 2 level number of nodes. For
example at level 2 there must be 2 2 = 4 nodes and at level 3
there must be 23 = 8 nodes.
A binary tree in which every internal node has exactly two
children and all leaf nodes are at same level is called
Complete Binary Tree.
Extended Binary Tree
A binary tree can be converted into Full Binary tree by adding dummy nodes to existing nodes wherever required.
The full binary tree obtained by adding dummy nodes to a binary tree is called as Extended Binary Tree.
Binary Tree Representations
A binary tree data structure is represented using two methods. Those methods are as follows...
1.Array Representation
2.Linked List Representation
Consider the following binary tree...
To represent a binary tree of depth 'n' using array representation, we need one dimensional array with a
maximum size of 2n + 1.
Linked List Representation of Binary Tree
Draw the binary tree having the following Draw the memory representation of the binary
memory representation: tree given below.
Given the memory representation of a tree that stores the names of family members, construct the corresponding
tree from the given data.
Sequential representation of binary trees:
• Sequential representation of trees is done using single or one-dimensional
arrays. Though it is the simplest technique for memory representation, it is
inefficient as it requires a lot of memory space.
• A sequential binary tree follows the following rules:
• A one-dimensional array, called TREE, is used to store the elements of
tree.
• The root of the tree will be stored in the first location. That is, TREE[1]
will store the data of the root element.
• The children of a node stored in location K will be stored in locations (2 ×
K) and (2 × K+1).
• The maximum size of the array TREE is given as (2^h –1), where h is the
height of the tree.
• An empty tree or sub-tree is specified using NULL. If TREE[1] = NULL,
then the tree is empty.
Creating a binary tree from a general tree:
The rules for converting a general tree to a binary tree are given below. Note that a general tree is converted
into a binary tree and not a binary search tree.
Rule 1: Root of the binary tree = Root of the general tree
Rule 2: Left child of a node = Leftmost child of the node in the binary tree in the general tree
Rule 3: Right child of a node in the binary tree = Right sibling of the node in the general tree
Now let us build the binary tree.
Step 1: Node A is the root of the general tree, so it will also be the root of the binary tree.
Step 2: Left child of node A is the leftmost child of node A in the general tree and right child of node A
is the right sibling of the node A in the general tree. Since node A has no right sibling in the general
tree, it has no right child in the binary tree.
Step 3: Now process node B. Left child of B is E and its right child is C (right sibling in general tree).
Step 4: Now process node C. Left child of C is F (leftmost child) and its right child is D (right sibling
in general tree).
Step 5: Now process node D. Left child of D is I (leftmost child). There will be no right child of D
because it has no right sibling in the general tree.
Step 6: Now process node I. There will be no left child of I in the binary tree because I has no left
child in the general tree. However, I has a right sibling J, so it will be added as the right child of I.
Step 7: Now process node J. Left child of J is K (leftmost child).
There will be no right child of J because it has no right sibling in the general tree
Step 8: Now process all the unprocessed nodes (E, F, G, H, K) in the same
%–+ab*cd/^ef–gh
• ^+/ab*cd/%fg–hi
TRAVERSAL ORDER: A, B, D, G, H, L, E, C, F, I, J, and K TRAVERSAL
ORDER: A, B, D, C, E, F, G, H, and I
• In-order Traversal:
• To traverse a non-empty binary tree in in-order, the following operations are performed recursively at each
node. The algorithm works by:
• Traversing the left sub-tree,
• Visiting the root node, and finally
• Traversing the right sub-tree.
• Consider the tree shown in Fig. The in-order traversal of the tree is given as B, A, and C. Left sub-tree first,
the root node next, and then the right sub-tree.
• In-order traversal is also called as symmetric traversal. In this algorithm, the left sub-tree is always traversed
before the root node and the right sub-tree.
• The word ‘in’ in the in-order specifies that the root node is accessed in between the left and the right sub-
trees. In-order algorithm is also known as the LNR traversal algorithm (Left-Node-Right).
• In-order traversal algorithm is usually used to display the elements of a binary search tree.
TRAVERSAL ORDER: G, D, H, L, B, E, A, C, I, F, K, and J
TRAVERSAL ORDER: B, D, A, E, H, G, I, F, and C
Post-order Traversal
To traverse a non-empty binary tree in post-order, the following operations are performed recursively at each node.
The algorithm works by:
1. Traversing the left sub-tree,
2. Traversing the right sub-tree, and finally
3. Visiting the root node.
Consider the tree shown in Fig. The post-order traversal of the tree is given as B, C, and A. Left sub-tree first, the
right sub-tree next, and finally the root node.
In this algorithm, the left sub-tree is always traversed before the right sub-tree and the root node. The word ‘post’
in the post-order specifies that the root node is accessed after the left and the right sub-trees.
Post-order algorithm is also known as the LRN traversal algorithm (Left-Right-Node).
Post-order traversals are used to extract postfix notation from an expression tree.
TRAVERSAL ORDER: G, L, H, D, E, B, I, K, J, F, C, and A
TRAVERSAL ORDER: D, B, H, I, G, F, E, C, and A
Constructing a Binary Tree from Traversal Results:
We can construct a binary tree if we are given at least two traversal results. The first traversal must be the in-order
traversal and the second can be either pre-order or post-order traversal.
The in-order traversal result will be used to determine the left and the right child nodes, and the pre-order/post-
order can be used to determine the root node.
For example, consider the traversal results given below:
In–order Traversal: D B E A F C G
Pre–order Traversal: A B D E C F G
Follow the steps given below to construct the tree:
Step 1 Use the pre-order sequence to determine the root node of the tree. The first element would be the root node.
Step 2 Elements on the left side of the root node in the in-order traversal sequence form the left sub-tree of the root
node. Similarly, elements on the right side of the root node in the in-order traversal sequence form the right sub-
tree of the root node.
Step 3 Recursively select each element from pre-order traversal sequence and create its left and right sub-trees
from the in-order traversal sequence.
Look at Fig. which constructs the tree from its traversal results.
Now consider the in-order traversal and post-order traversal sequences of a given binary tree. Before constructing
the binary tree, remember that in post-order traversal the root node is the last node. Rest of the steps will be the
same as mentioned above Fig.
In–order Traversal: D B H E I A F J C G
Post order Traversal: D H I E B J F G C A
In–order Traversal: D B H E I A F J C G
Post order Traversal: D H I E B J F G C A
APPLICATIONS OF TREES :
• Trees are used to store simple as well as complex data. Here simple means an integer value, character value
and complex data means a structure or a record.
• Trees are often used for implementing other types of data structures like hash tables, sets, and maps.
• A self-balancing tree, Red-black tree is used in kernel scheduling, to preempt massively multi-processor
computer operating system use.
• Another variation of tree, B-trees are prominently used to store tree structures on disc. They are used to index
a large number of records.
• B-trees are also used for secondary indexes in databases, where the index facilitates a select operation to
answer some range criteria.
• Trees are an important data structure used for compiler construction.
• Trees are also used in database design.
• Trees are used in file system directories.
• Trees are also widely used for information storage and retrieval in symbol tables
BINARY SEARCH TREE
a binary search tree is a binary tree with the following properties:
• The left sub-tree of a node N contains values that are less than N’s
value.
• The right sub-tree of a node N contains values that are greater than N’s
value.
• Both the left and the right binary trees also satisfy these properties and,
thus, are binary search trees.
State whether the binary trees in Fig. are binary search trees or not.
Create a binary search tree using the following data elements:
45, 39, 56, 12, 34, 78, 32, 10, 89, 54, 67, 81
OPERATIONS ON BINARY SEARCH TREES
Searching for a Node in a Binary Search Tree
• The search function is used to find whether a given value is present in the tree or not. The searching process
begins at the root node.
• The function first checks if the binary search tree is empty. If it is empty, then the value we are searching for
is not present in the tree. So, the search algorithm terminates by displaying an appropriate message.
• However, if there are nodes in the tree, then the search function checks to see if the key value of the current
node is equal to the value to be searched.
• If not, it checks if the value to be searched for is less than the value of the current node, in which case it
should be recursively called on the left child node.
• In case the value is greater than the value of the current node, it should be recursively called on the right
child node.
Searching a node with value 12 in the given binary search tree