CH-4

Trees
Introduction

• A tree is an ideal data structure for representing

hierarchical data.
• A tree can be theoretically defined as a finite set of
one or more data items (or nodes) .
• A tree consists of nodes with a parent-child
relation.
• Nodes are linked by edges.
• A tree consists of finite set of elements, called
nodes, and a finite set of lines called branches, that
connect the nodes. 1
 Tree Terminologies
Consider the following tree.

• Root: a node with out a parent. A

• External (leaf) node: a node without a child.
 C, D, E, H, K, L, M, G
• Ancestors of a node: An ancestor of a node is
either the node’s parent or any ancestor of the
node’s parent i.e. parent, grandparent, grand-
grandparent, etc of a node.
• Ancestors of K  A, F, I
2
• Descendants of a node: children, grandchildren,
grand-grandchildren etc of a node. Descendants of F
 H, I, J, K, L, M
• Sibling Nodes: children of the same parent are
called sibling. Example: C,D.
• Depth of a node: number of ancestors or length of
the path from the root to the node.
• The level of a node is its distance from the root. The
root is at level 0, its children are at level 1, etc. …
• Degree of a node: The number of nodes connected
to any node is called the degree of that node , or we
can say that the number of children any node
contains is the degree of that node. 3
Contd…

• Degree of a tree: The maximum degree of any

node can be taken as the degree of that tree.
• Subtree: a tree consisting of a node and its
descendants.

4
 Binary Trees
• A binary tree is a tree in which no
node can have more than two sub-
trees; the maximum out-degree for a
node is two.
• In other words, a node can have zero,
one, or two sub-trees.
• These subtrees are designated as the
left sub-tree and the right sub-tree.
• A binary tree is made of nodes,
where each node contains a "left"
pointer, a "right" pointer, and a data
element. 5
 Types of BT
• Full binary tree: a binary tree where each
node has either 0 or 2 children.
• A binary tree T is full if each node is either a
leaf or possesses exactly two child nodes.
• Almost Complete BT: a binary tree T with
n levels is complete if all levels except
possibly the last are completely full, and
the last level has all its nodes to the left
side.
• Balanced BT (strictly complete BT): is a BT where
each node except the leaf nodes has left and right
children and all the leaves are at the same level.
• The maximum nodes at any level n are 2n , where n is
the level number.
6
 Operations of a binary tree
• The basic operations commonly performed in
a binary tree are:
 Create an empty binary tree
 Traversing a binary tree
 Inserting a new node
 Deleting a node
 Displaying
Etc…
7
 TRAVERSING BINARY TREES (RECURSIVELY)

• Tree traversal is one of the most common operations

performed on tree data structures.
• It is a way in which each node in the tree is visited
exactly once in a systematic manner.
• There are three standard ways of traversing a binary
tree. They are:
1. Pre Order Traversal (root – left - right)
2. In order Traversal (Left – root - right)
3. Post Order Traversal (Left – right - root)
8
 PRE ORDERS TRAVERSAL RECURSIVELY
Step 1: Start from the root node . Write it down.
Step 2: Now go to the leftmost node from the root node in
the left sub tree. On it’s way to the left most node, right
down all the nodes as it comes.
Step 3: When the leftmost node is reached. Write it down.
Step 4: Now visit the right sub tree of the leftmost node’s
parent node.
Step 5: Write down the first node of the right sub tree.
Step 6: Now proceed in the same way as in Step 2 - 5 till
writing down of all the nodes is finished.
9
10
 Contd.
.

11
 Exercise

• Traverse the following tree using pre-order

traversal method.

13
 IN ORDER TRAVERSAL RECURSIVELY

• The in order traversal of a non-empty binary

tree is defined as follows :
1. Traverse the left sub tree in order
2. Visit the root node
3. Traverse the right sub tree in order
In order traversal, the left sub tree is traversed
recursively, before visiting the root.
After visiting the root the right sub tree is
traversed recursively, in order fashion.

14
 Exercise
• Traverse the following tree using In-order
traversal method.

17
 POST ORDER TRAVERSAL RECURSIVELY

• The post order traversal of a non-empty

binary tree can be defined as :
1. Traverse the left sub tree in post order
2. Traverse the right sub tree in post order
3. Visit the root node

18
 Exercise
• Traverse the following tree using post-order
traversal method.

21
 Binary Search Trees
• Binary Search Trees (BST) are a type of Binary
Trees with a special organization of data.
• A Binary Search Tree is a binary tree with the
following properties:
All items in the left subtree are less than the
root.
All items in the right subtree are greater or
equal to the root.
Each subtree is itself a binary search tree.
22
 Basic Property
• In a binary search tree,
the left subtree contains key values less than
the root
the right subtree contains key values greater
than or equal to the root.

23
 Contd.
• Binary Search Tree can be implemented as a
linked data structure in which each node is an
object with three pointer fields.
• The two pointer fields left and right point to
the nodes corresponding to the left child and
right child respectively .
• NIL in any pointer field signifies that there
exists no corresponding child.

24
Contd.

25
Valid BST(example)

26
Contd.

27
 Construction of a BST
• Construct the BST of :
58,76,14,63,63,78,43,6,11,61.
Solution:
Step 1: initially, the tree is empty so place the
first number at the root.
58

28
 Contd.
Step2: compare the next number (76) with the
root. If the incoming number is greater than or
equal to the root then place it in the right
child position, otherwise place it into the left
child position.

58

76

29
 Contd.
Step 3: compare the next number (14)with the
root. This is less than the root so examine the
left subtree.

58

14 76

30
 Contd.
Step 4: now, the next incoming number 63 is
greater than 58 so go to the right sub tree
where compare it with 76. since 63<76 so
place it in the left child’s position of 76.

58

14 76

63

31
 Contd.
Step 5: Repeat the process for the next number
63.
58

14 76

63

63

32
 Contd.
Step 6: Repeat the process for the next number
78.
58

14 76

63 78

63

33
 Contd.
Step 7: Repeat the process for the next number
43
58

14 76

63 78
43

63

34
 Contd.
Step 8: Repeat the process for the next number
6
58

14 76

63 78
6 43

63

35
 Contd.
Step 9: Repeat the process for the next number
11
58

14 76

63 78
6 43

63
11

36
 Contd.
Step 10: Repeat the process for the next number
61
58

14 76

63 78
6 43

63
11 61

37
 Exercise
• Construct the BST of :
14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5

38
 BST Operations
• We discuss four basic BST operations:
traversal, search, insert, and delete; and
develop algorithms for searches, insertion, and
deletion.
• Travers
• Search
• Insertion
• Deletion
39
 BST declaration
struct tree{
int info;
struct tree*left;
struct tree*right;
};
typedef struct tree *ptr;

40
 Create a BST

/* A function that creates,

initializes,* and returns a new node
*/
bst_node *CreateANode(int val){
struct tree *ptr;
*ptr=(struct tree *)malloc(sizeof(struct tree));
ptr ->data = val;
ptr ->right= ptr->left=NULL;
return ptr;
}
41
 Cont…
/* pre-order traversal
void preOrder(bst_node *root) {
if(root == NULL) {return;}
visit(root); // visit the root node
preOrder(root->left)
preOrder(root->right
}

42
Cont…
/*Post-order traversal*/
void postOrder(bst_node *root)
{
if(root == NULL) {return;}
postOrder(root->left);
postOrder(root->right);
visit(root);
}

43
Cont…
/* In-order traversal
void InOrder(bst_node *root) {
if(root == NULL) {return;}
InOrder(root->left);
Visit(root);
InOrder(root->right);
}

44
 SEARCHING THROUGH THE BINARY SEARCH TREE
• Searching operation of the binary search tree is always in
downward direction.
• Use the search key to direct a recursive binary search for a
matching node
1. Start at the root as current node
2. If the search key’s value matches the current node’s key,
then - match found!
3. If search key’s value is greater than current node’s key,
i. If the current node has a right child, search right
ii. Else, no matching node in the tree
4. If search key is less than the current node’s key,
i. If the current node has a left child, search left
ii. Else, no matching node in the tree
45
Searching Algorithm in BST

46
 Contd.
Altenative ALGORITHM
[Link] the DATA to be searched and assign the
address of the root node to ROOT.
[Link] (DATA == ROOT→Info)
(a)Display “The DATA exist in the tree”
Exit
[Link] (ROOT == NULL)
(a)Display “The DATA does not exist”
Exit
[Link](DATA > ROOT→Info)
(a)ROOT = ROOT→RChild
(b)GoTo Step 2
[Link](DATA < ROOT→Info)
(a)ROOT = ROOT→Lchild
(b)GoTo Step 2
47
[Link]
 INSERTING A NODE

• A BST is constructed by the repeated insertion

of new nodes to the tree structure. Inserting a
node in to a tree is achieved by performing
two separate operations.
1. The tree must be searched to determine
where the node is to be inserted.
2. Then the node is inserted into the tree.

48
49
Algorithm

50
 Alternative Algorithm – Insert new node

Step 1: Compare DATA with root node information

of the tree
(a) If the Tree is Empty
Set the root to a new node
(b) If (DATA < ROOT→Info) Proceed to left
(c) If (DATA > =ROOT→Info) Proceed to right
Step 2: Repeat Step 1 until we meet an empty sub
tree, where we can insert the new node
Step 3: Exit
51
 DELETING A NODE
• When deleting a node, any of the following
conditions arises:
1. The node to be deleted has no children
2. The node has exactly one child or sub tree
3. The node has two children or two sub trees

52
 Contd.
• Case 1:
-The node to be deleted has no children – leaf node
-All we need to do is,
=> set the parent’s deleted sub-tree to null and free
the leaf node
• Case 2:
-The node to be deleted has only a right subtree
-If there is only a right subtree, then we can simply
attach the right subtree to the deleted node’s parent.

53
 Contd.

• Case 3 :
-The node to be deleted has only a left subtree .
-If there is only a left subtree, then we attach the left subtree to
the deleted node’s parent.
Case 4 :
- The node to be deleted has two subtrees .
-We try to maintain the existing structure as much as
possible by finding data to take the deleted data’s place. This
can be done in one or two ways:
1. find the largest node in the deleted node’s left subtree and
move its data to replace the deleted node’s data, or
2. find the smallest node on the deleted node’s right subtree
and move its data to replace the deleted nodes data.

54
Contd.

55
Contd.

56
 Removal in BST: Example

Case 1: removing a node with 2 EMPTY SUBTREES

parent
7

cursor
5 9

4 6 8 10

7
Removing 4
replace the link in the parent
with null 5 9

8 10 57
6
 Removal in BST: Example

Case 2: removing a node with 1 EMPTY SUBTREE

the node has no left child:

link the parent of the node to the right (non-empty) subtree
Removing 5

parent
parent

7 7
cursor

5 9 cursor 5 9

6 8 10 6 8 10
58
 Removal in BST: Example

Case 3: removing a node with 1 EMPTY SUBTREE

the node has no right child:

link the parent of the node to the left (non-empty) subtree

Removing 5
parent
parent

7 cursor 7
cursor

5 9 5 9

4 8 10 4 8 59 10
 Removal in BST: Example

Case 4: removing a node with 2 SUBTREES

- replace the node's value with the max value in the left subtree
- delete the max node in the left subtree

Removing 7
cursor
cursor

7 6

5 9 5 9

4 6 8 10 4 8 60 10
EXERCISE

61
 EXPRESSION TREE
 The binary tree corresponding to the mathematical
expressions is called expression tree.
 A special kind of binary tree in which:

1. Each leaf node contains a single operand

2. Each nonleaf node contains a single binary operator
3. The left and right subtrees of an operator node
represent subexpressions that must be evaluated
before applying the operator at the root of the
subtree.
 The expression trees are constructed by using the
operands, the operators and their order of precedence
and associative law of operators. 62
 Binary Expression

‘*’

‘-’ ‘/’

‘8’ ‘5’ ‘+’ ‘3’

‘4’ ‘2’

63
 Example
• Construct the expression tree for the
expression
a*(b+c)/d-e
Solution:
Step 1: first the parenthesis is evaluated so
construct the tree for (b+c)
+

b c

64
 Contd.
• Step 2: the result of (b+c) will be multiplied by
a so now construct the expression tree for
a*(b+c).
*

+
a

b c

65
 Contd.
• Step 3: the result of a*(b+c) will be divided by
d so now construct the expression tree for
a*(b+c)/d.
/

d
*

+
a

b c

66
 Contd.
• Step 4: operand e is substructed from the
result of a*(b+c)/d so now construct the
expression tree for a*(b+c)/d-e.
-

e
/

d
*

a +

b c

Exercise: Build and expression tree for:

• (A - B + C) * (-D)
67
 Traversals

• Since expression is also a binary tree, it can be

traversed in three different ways:
(1) in-order
(2) pre-order
(3) post-order
• This traversal techniques of the expression tree
produce the different forms of the arithmetic
expression.
• When the expression tree is traversed in the in-order,
pre-order or post order way, it produces the infix,
prefix or postfix form of the expression respectively.

68
 example
• Consider the following expression tree and
traverse in order, preorder and post order.
-

e
/

d
*

+
a

b c

69
 Solution
• In-order traversal: ((a*(b+c))/d)-e
• Pre-order traversal: -/*a+bcde
• Post-order traversal: abc+*d/e-

70
 Exersise
• Consider the following expression tree and
traverse in order, preorder and post order.
‘*’

‘-’ ‘/’

‘8’ ‘5’ ‘+’ ‘3’

‘4’ ‘2’
71
 Exercise
• Consider the following tree and traverse in
order, preorder and post order.

72