UNIT II - TREE

TREE
• Tree is a non-linear data structure which organizes data in a
hierarchical structure and this is a recursive definition.
• A tree is a connected graph without any circuits.
• If in a graph, there is one and only one path between every
pair of vertices, then graph is called
Properties
• The first node from where the tree originates is called as a root
node.
• In any tree, there must be only one root node.
• We can never have multiple root nodes in a tree data structure.
• Example-
• Here, node A is the only root node.
Properties
Edge
• The connecting link between any two nodes is called as an edge.
• In a tree with n number of nodes, there are exactly (n-1) number
of edges.
Properties
Parent
• The node which has a branch from it to any other node is called
as a parent node.
• In other words, the node which has one or more children is
called as a parent node.
• In a tree, a parent node can have any number of child nodes.

•Node A is the parent of nodes B and C

•Node B is the parent of nodes D, E and F
•Node C is the parent of nodes G and H
•Node E is the parent of nodes I and J
•Node G is the parent of node K
Properties
• Child-
• The node which is a descendant of some node is called as a child
node.
• All the nodes except root node are child nodes.
.

Nodes B and C are the children of node A

Nodes D, E and F are the children of node B
Nodes G and H are the children of node C
Nodes I and J are the children of node E
Node K is the child of node G
Properties
Siblings
• Nodes which belong to the same parent are called as siblings.
• In other words, nodes with the same parent are sibling nodes.
.

Nodes B and C are siblings

Nodes D, E and F are siblings
Nodes G and H are siblings
Nodes I and J are siblings
Properties
Degree
• Degree of a node is the total number of children of that node.
• Degree of a tree is the highest degree of a node among all the
nodes in the tree.
Degree of node A = 2
Degree of node B = 3
Degree of node C = 2
Degree of node D = 0
Degree of node E = 2
Degree of node F = 0
Degree of node G = 1
Degree of node H = 0
Degree of node I = 0
Degree of node J = 0
Degree of node K = 0
Properties
Internal Node
• The node which has at least one child is called as an internal node.
• Internal nodes are also called as non-terminal nodes.
• Every non-leaf node is an internal node.

Here, nodes A, B, C, E and G are internal nodes

Properties
Leaf Node
• The node which does not have any child is called as a leaf node.
• Leaf nodes are also called as external nodes or terminal nodes.

Here, nodes D, I, J, F, K and H are leaf nodes.

Properties
Level
• In a tree, each step from top to bottom is called as level of a tree.
• The level count starts with 0 and increments by 1 at each level or step.
Properties
Height-
• Total number of edges that lies on the longest path from any leaf node to a
particular node is called as height of that node.
• Height of a tree is the height of root node.
• Height of all leaf nodes = 0

Height of node A = 3
Height of node B = 2
Height of node C = 2
Height of node D = 0
Height of node E = 1
Height of node F = 0
Height of node G = 1
Height of node H = 0
Height of node I = 0
Height of node J = 0
Height of node K = 0
Properties
Depth
• Total number of edges from root node to a particular node is called as depth of that node.
• Depth of a tree is the total number of edges from root node to a leaf node in the longest path.
• Depth of the root node = 0
• The terms “level” and “depth” are used interchangeably.

Depth of node A = 0
Depth of node B = 1
Depth of node C = 1
Depth of node D = 2
Depth of node E = 2
Depth of node F = 2
Depth of node G = 2
Depth of node H = 2
Depth of node I = 3
Depth of node J = 3
Depth of node K = 3
Properties
Subtree
• In a tree, each child from a node forms a subtree recursively.
• Every child node forms a subtree on its parent node.
Properties
Forest
• A forest is a set of disjoint trees.
Binary Tree
• Binary tree is a special tree data structure in
which each node can have at most 2 children.
• Thus, in a binary tree,
• Each node has either 0 child or 1 child or 2
children.
Unlabeled Binary Tree
• A binary tree is unlabeled if its nodes are not
assigned any label

Example-
Consider we want to draw all the binary trees possible with 3
unlabeled nodes.
Using the above formula, we have-

Number of binary trees possible with 3 unlabeled nodes

= 2 x 3C3 / (3 + 1)
= 6C3 / 4
=5
labeled Binary Tree
• A binary tree is labeled if all its nodes are
assigned a label.

Example-
Consider we want to draw all the binary trees possible with 3
labeled nodes.
Using the above formula, we have-

Number of binary trees possible with 3 labeled nodes

= { 2 x 3C3 / (3 + 1) } x 3!
= { 6C3 / 4 } x 6
=5x6
= 30
labeled Binary Tree
• A binary tree is labeled if all its nodes are
assigned a label.

Example-
Consider we want to draw all the binary trees possible with 3
labeled nodes.
Using the above formula, we have-

Number of binary trees possible with 3 labeled nodes

= { 2 x 3C3 / (3 + 1) } x 3!
= { 6C3 / 4 } x 6
=5x6
= 30
Thus,
• With 3 labeled nodes, 30 labeled binary trees are possible.
• Each unlabeled structure gives rise to 3! = 6 different labeled structures.
Types of Binary Trees
• Rooted Binary Tree
• A rooted binary tree is a binary tree that
satisfies the following 2 properties-
• It has a root node.
• Each node has at most 2 children
Full / Strictly Binary Tree-
• A binary tree in which every node has either 0
or 2 children is called as a Full binary tree.
• Full binary tree is also called as Strictly binary
tree.

•First binary tree is not a full binary tree.

•This is because node C has only 1 child.
Complete / Perfect Binary Tree-
• A complete binary tree is a binary tree that satisfies
the following 2 properties-
• Every internal node has exactly 2 children.
• All the leaf nodes are at the same level.
• Complete binary tree is also called as Perfect binary
tree.

First binary tree is not a complete binary

This is because all the leaf nodes are not at the same
level.
Almost Complete Binary Tree-
• An almost complete binary tree is a binary tree
that satisfies the following 2 properties-
• All the levels are completely filled except possibly
the last level.
• The last level must be strictly filled from left to
right.

First binary tree is not an almost complete binary tree.

This is because the last level is not filled from left to
right.
• Skewed Binary Tree-
• A skewed binary tree is a binary tree that satisfies the
following 2 properties-
• All the nodes except one node has one and only one child.
• The remaining node has no child.
• A skewed binary tree is a binary tree of n nodes such that
its depth is (n-1).
Tree Traversal
• Tree Traversal refers to the process of visiting
each node in a tree data structure exactly
once.
Various tree traversal techniques are-
Tree Traversal
Inorder Traversal-
Algorithm-
Traverse the left sub tree i.e. call Inorder (left sub tree)
Visit the root
Traverse the right sub tree i.e. call Inorder (right sub tree)

Left → Root → Right

Applications-

Inorder traversal is used to

get infix expression of an
expression tree.
Tree Traversal
Preorder Traversal-
Algorithm-

Visit the root

Traverse the left sub tree i.e. call Preorder (left sub tree)
Traverse the right sub tree i.e. call Preorder (right sub tree)

Root → Left → Right

Tree Traversal
Postorder Traversal-
Algorithm-
Traverse the left sub tree i.e. call Postorder (left sub tree)
Traverse the right sub tree i.e. call Postorder (right sub tree)
Visit the root

Left → Right → Root

Application
•Postorder traversal is used
to get postfix expression of
an expression tree.
•Postorder traversal is used
to delete the tree.
•This is because it deletes
the children first and then it
deletes the parent.
Tree Traversal
• Breadth First Traversal-
• Breadth First Traversal of a tree prints all the nodes of a tree level by level.
• Breadth First Traversal is also called as Level Order Traversal.
•

Application-

Level order traversal is used

to print the data in the same
order as stored in the array
representation of a
complete binary tree.
Problems

Which of the following binary trees has

its inorder and preorder traversals as
BCAD and ABCD respectively
Representation
• A binary tree data structure is represented
using two methods. Those methods are as
follows...
• Array Representation
• Linked List Representation
Array Representation
Linked List Representation
Properties of Binary Tree
• At each level of i, the maximum number of nodes is 2i.
• In general, the maximum number of nodes possible at height h
is (20 + 21 + 22+….2h) = 2h+1 -1.
Therefore, the maximum number of nodes at height 3 is equal
to (1+2+4+8) = 15.
• 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.
Properties of Full Binary Tree
• The number of leaf nodes is equal to the number of internal
nodes plus 1.
– If the number of internal nodes is 5; therefore, the number of leaf
nodes is equal to 6.
• The maximum number of nodes is the same as the number of
nodes in the binary tree, i.e., 2h+1 -1.
• The minimum number of nodes in the full binary tree is 2*h-1.
• The minimum height of the full binary tree is log2(n+1) - 1.
• The maximum height of the full binary tree can be computed
as:
– n= 2*h - 1
– n+1 = 2*h
– h = n+1/2
Properties of Complete Binary Tree

• The maximum number of nodes in complete

binary tree is 2h+1 - 1.
• The minimum number of nodes in complete
binary tree is 2h.
• The minimum height of a complete binary
tree is log2(n+1) - 1.
• The maximum height of a complete binary
tree is
Expression tree
• Expression trees are used to express a mathematical
expression in the form of a binary tree.
• Expression trees are binary trees in which each internal (non-
leaf) node is an operator and each leaf node is an operand.
Construction of Expression Tree
• For constructing an expression tree we use a stack. We loop through input expression and
do the following for every character.
• If a character is an operand push that into the stack
• If a character is an operator pop two values from the stack make them its child and push
the current node again.
• In the end, the only element of the stack will be the root of an expression tree.

• Input: A B C*+ D/
• Output: A + B * C / D
postfix notation is: m n * p q r + * +
postfix notation is: m n * p q r + * +
postfix notation is: m n * p q r + * +
Binary Search Tree
• We have discussed-
– Binary tree is a special tree data structure.
– In a binary tree, each node can have at most 2 children.
– In a binary tree, nodes may be arranged in any random order.
Binary Search Tree is a special kind of binary tree in which nodes are arranged in
a specific order.
In a binary search tree (BST), each node contains-
– Only smaller values in its left sub tree
– Only larger values in its right sub tree
Number of Binary Search Trees

Example-
Number of distinct binary search trees possible with 3 distinct keys

= 2×3C3 / 3+1
= 6C3 / 4
=5

If three distinct keys are A, B and C, then 5 distinct binary search trees are-
Binary Search Tree Construction
Example-
Construct a Binary Search Tree (BST) for the following
sequence of numbers-
50, 70, 60, 20, 90, 10, 40, 100
• When elements are given in a sequence,
• Always consider the first element as the root node.
• Consider the given elements and insert them in the
BST one by one.
• The binary search tree will be constructed as
explained below-
• Insert 50-
Insert 70
As 70 > 50, so insert 70 to the right of 50.
Binary Search Tree Construction
Example- 50, 70, 60, 20, 90, 10, 40, 100
•

Insert 50

Insert 70
As 70 > 50, so insert 70 to the right of 50.

Insert 60
• As 60 > 50, so insert 60 to the right of 50.
• As 60 < 70, so insert 60 to the left of 70.
Binary Search Tree Construction
Example- 50, 70, 60, 20, 90, 10, 40, 100
•
Insert 20-

•As 20 < 50, so insert 20 to the left of 50.

Insert 90-

•As 90 > 50, so insert 90 to the right of 50.

•As 90 > 70, so insert 90 to the right of 70.

Insert 10-

•As 10 < 50, so insert 10 to the left of 50.

•As 10 < 20, so insert 10 to the left of 20.
Binary Search Tree Construction
Example- 50, 70, 60, 20, 90, 10, 40, 100
•
Insert 40-

•As 40 < 50, so insert 40 to the left of 50.

•As 40 > 20, so insert 40 to the right of 20.

Insert 100-

•As 100 > 50, so insert 100 to the right of 50.

•As 100 > 70, so insert 100 to the right of 70.
•As 100 > 90, so insert 100 to the right of 90.
Problems
• A binary search tree is generated by inserting
in order of the following integers-
• 50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24
BINARY SEARCH TREE TRAVERSAL
• A binary search tree is traversed in exactly the same way a binary tree is
traversed.
• In other words, BST traversal is same as binary tree traversal.
• Example- Preorder Traversal-

100 , 20 , 10 , 30 , 200 , 150 , 300

Inorder Traversal-

10 , 20 , 30 , 100 , 150 , 200 , 300

Postorder Traversal-

10 , 30 , 20 , 150 , 300 , 200 , 100

Unlike Binary Trees,

•A binary search tree can be constructed using only preorder or only postorder traversal result.
•This is because inorder traversal can be obtained by sorting the given result in increasing order .
BINARY SEARCH TREE OPERATIONS

Search Operation

Rules-
• For searching a given key in the BST,
•Compare the key with the value of root node.
•If the key is present at the root node, then return the root node.
•If the key is greater than the root node value, then recur for the root node’s right subtree.
•If the key is smaller than the root node value, then recur for the root node’s left subtree.
• Consider key = 45 has to be searched in the given BST

•We start our search from the root node 25.

•As 45 > 25, so we search in 25’s right subtree.
•As 45 < 50, so we search in 50’s left subtree.
•As 45 > 35, so we search in 35’s right subtree.
•As 45 > 44, so we search in 44’s right subtree but 44 has no subtrees.
•So, we conclude that 45 is not present in the above BST.
Insertion Operation
• Insertion Operation is performed to insert an element
in the Binary Search Tree.
• Rules:
• The insertion of a new key always takes place as the
child of some leaf node.
• For finding out the suitable leaf node,
• Search the key to be inserted from the root node till
some leaf node is reached.
• Once a leaf node is reached, insert the key as child of
that leaf node.
Example
• Consider the following example where key = 40 is
inserted in the given BST

•We start searching for value 40 from the root node 100.
•As 40 < 100, so we search in 100’s left subtree.
•As 40 > 20, so we search in 20’s right subtree.
•As 40 > 30, so we add 40 to 30’s right subtree.
Deletion Operation
• Deletion Operation is performed to delete a particular element from the
Binary Search Tree.
Case-01: Deletion Of A Node Having No Child (Leaf Node)-
• Just remove / disconnect the leaf node that is to deleted from the tree .

Example
Consider the following example where node with value = 20 is deleted from
the BST
Deletion Operation
Case-02: Deletion Of A Node Having Only One Child-
• Just make the child of the deleting node, the child of its grandparent.
Example-
• Consider the following example where node with value = 30 is deleted
from the BST
Deletion Operation
Case-03: Deletion Of A Node Having Two Children-
A node with two children may be deleted from the BST in the following two
ways-
Method-01:
Visit to the right subtree of the deleting node.
Pluck the least value element called as inorder successor.
Replace the deleting element with its inorder successor.
Example-
Consider the following example where node with value = 15 is deleted from
the BST
Deletion Operation
Case-03: Deletion Of A Node Having Two Children-
A node with two children may be deleted from the BST in the following two
ways-
Method-02:
Visit to the left subtree of the deleting node.
Pluck the greatest value element called as inorder predecessor.
Replace the deleting element with its inorder predecessor.
Example-
Consider the following example where node with value = 15 is deleted from
the BST-
AVL Tree
• AVL trees are special kind of binary search trees.
• In AVL trees, height of left subtree and right subtree of every node differs
by at most one.
• AVL trees are also called as self-balancing binary search trees.

This tree is an AVL tree

because-
•It is a binary search tree.
•The difference between
height of left subtree and
right subtree of every node is
at most one.
Balance Factor-
Balance factor is defined for every node.
Balance factor of a node = Height of its left
subtree – Height of its right subtree
Balance factor of every node is either 0 or 1 or -
1.
AVL Tree Operations
Like BST Operations, commonly performed operations on AVL tree are-
– Search Operation
– Insertion Operation
– Deletion Operation
• After performing any operation on AVL tree, the balance factor of each node is
checked.
• There are following two cases possible-
Case-01:
• After the operation, the balance factor of each node is either 0 or 1 or -1.
• In this case, the AVL tree is considered to be balanced.
• The operation is concluded.
Case-02:
• After the operation, the balance factor of at least one node is not 0 or 1 or -1.
• In this case, the AVL tree is considered to be imbalanced.
• Rotations are then performed to balance the tree.
AVL Tree Rotations
• Rotation is the process of moving the nodes to make tree
balanced
• There are 4 kinds of rotations possible in AVL Trees
Cases Of Imbalance And Their Balancing Using Rotation Operations

Case-01:
Cases Of Imbalance And Their Balancing Using Rotation Operations

Case-02:
Cases Of Imbalance And Their Balancing Using Rotation Operations

Case-03:
Cases Of Imbalance And Their Balancing Using Rotation Operations

Case-04:
AVL Tree Properties
Property-01:
Maximum possible number of nodes in AVL tree of height H = 2 H+1 – 1
Example-
Maximum possible number of nodes in AVL tree of height-3
= 23+1 – 1
= 16 – 1
= 15
Thus, in AVL tree of height-3, maximum number of nodes that can be inserted = 15.
AVL Tree Properties
Property-02:
• Minimum number of nodes in AVL Tree of height H is given by a recursive relation-
• N(H) = N(H-1) + N(H-2) + 1
Base conditions for this recursive relation are-
• N(0) = 1
• N(1) = 2
Example
• Minimum possible number of nodes in AVL tree of height-3 = 7
AVL Tree Properties
Property-03:
• Minimum possible height of AVL Tree using N nodes = ⌊log2N⌋
Example
Minimum possible height of AVL Tree using 8 nodes
= ⌊log28⌋
= ⌊log223⌋
= ⌊3log22⌋
= ⌊3⌋
=3
Property-04:
• Maximum height of AVL Tree using N nodes is calculated using recursive relation-
N(H) = N(H-1) + N(H-2) + 1
Base conditions for this recursive relation are-
• N(0) = 1
• N(1) = 2
NOTE-
• If there are n nodes in AVL Tree, its maximum height can not exceed 1.44log2n.
• In other words, Worst case height of AVL Tree with n nodes = 1.44log2n.