HND in Computing and Software

Engineering
SEC5213: Data Structures and Algorithm
Level: 5
Credit Value: 20

Lesson 12 – Tree Data Structure

1
Lecturer: Ms. Sathananthy 06/04/2022
 Learning Outcomes 04
• Apply algorithms and data structures to solve programming problems.

2 06/04/2022
 Outline
 Fundamentals of tree DS

 Binary tree

 Binary search tree

 Basics of Binary tree and BST

 Develop algorithm

 Implementation

7 06/04/2022
 Tree Data Structure
 A Tree is a recursive data structure containing the set of one or more data nodes where one node is

designated as the root of the tree while the remaining nodes are called as the children of the root.

 The nodes other than the root node are partitioned into the non empty sets where each one of them is

to be called sub-tree.

 Nodes of a tree either maintain a parent-child relationship between them or they are sister nodes.

 In a general tree, A node can have any number of children nodes but it can have only a single parent.

 The following image shows a tree, where the node A is the root node of the tree while the other

nodes can be seen as the children of A.

4 06/04/2022
 Tree Data Structure – contd.

 A data structure accessed beginning at the root node Each node is either a leaf

node or an internal node. Internal nodes have one or more child nodes and is
called the parent of its children.
 All the children of the same parent are siblings. Contrary to a physical tree, the

root is usually depicted at the top of the structure, and the leaves are at the
bottom.
 A tree is either empty (with no nodes), or a root and zero or more sub-trees

5 06/04/2022
 Trees
A tree is either empty (with no nodes), or a root and zero or more sub-

trees.

6 06/04/2022
 Basic Terminology
 Root Node :- The root node is the topmost node in the tree hierarchy. In other

words, the root node is the one which doesn't have any parent.
 Sub Tree :- If the root node is not null, the tree T1, T2 and T3 is called sub-trees

of the root node.

 Leaf Node :- The node of tree, which doesn't have any child node, is called leaf

node. 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.
 Path :- The sequence of consecutive edges is called path. In the tree shown in

the above image, path to the node E is A→ B → E.

7 06/04/2022
 Basic Terminology
 Ancestor node :- An ancestor of a node is any predecessor node on a path from

root to that node. The root node doesn't have any ancestors. In the tree shown in
the above image, the node F have the ancestors, B and A.
 Degree :- Degree of a node is equal to number of children, a node have. In the

tree shown in the above image, the degree of node B is 2. Degree of a leaf node
is always 0 while in a complete binary tree, degree of each node is equal to 2.
 Level Number :- Each node of the tree is assigned a level number in such a way

that each node is present at one level higher than its parent. Root node of the tree
is always present at level 0
8 06/04/2022
 Binary Trees
A binary tree is made of nodes

Each node contains a left pointer and a right pointer and data element

The root pointer points to the top most node in the tree

The left and right pointers recursively points to the left and right sub-trees on

either side
A null pointer represents a binary tree with no nodes.(an empty tree)

A binary tree is either empty or is made of a single node, where the left and

right pointers each point to a binary tree

9 06/04/2022
 Types of Tree
The tree data structure can be classified into six different categories.

10 06/04/2022
 Binary Trees

Binary Tree is a special type of generic tree in which, each node can have

at most two children. Binary tree is generally partitioned into three disjoint
subsets.
Root of the node

left sub-tree which is also a binary tree.

Right binary sub-tree

11 06/04/2022
 Binary Trees

 Root node : the top most node of the tree

 Leaf node : a node with both left and right as NULL

12 06/04/2022
 Binary Search Trees (ordered binary tree)

A type of binary tree where all the nodes are arranged in order

For each node, all elements in its left sub-tree are less than or equal to the

node, and all the elements in its right sub-tree are greater than the node

A BST is different from a binary tree

BSTs are fast at insert and search

13 06/04/2022
 Binary Search Trees (BSTs)

14 06/04/2022
 Binary Search Trees (BSTs)

On average, a BST algorithm can locate a node in an N node tree in order log(N)

time (log base 2)

 BSTs are good for dictionary problem where the code inserts and looks up

information indexed by some key

The log(N) is an average case, it is possible for a tree to be much slower

depending on its shape

15 06/04/2022
 Binary Search Trees (BSTs)

A major advantage of BSTs is the related sorting algorithms and search algorithms

BSTs are fundamental DS used as sets, multi sets and associative arrays

If a BST allows duplicate values, then it represent a multi set

If a BST doesn’t allow duplicate values, then it represent a set with unique values

16 06/04/2022
 Binary Search Trees (BSTs)

 Operations on BST

Creating a tree

Inserting

Removing

Searching

Traversing

Clear (remove all the elements)

Display all the elements

17 06/04/2022
 Binary Search Trees

 In order traversal:

 Traverse the left sub-tree first, and then traverse the root and the right sub-tree

respectively. This procedure will be applied to each sub-tree of the tree recursively.

 Algorithm:

If there is a left child, visit it

Visit the node itself

If there is a right visit it

18 06/04/2022
 Binary Search Trees (BSTs)

 Post order traversal:

Traverse the left sub-tree and then traverse the right sub-tree and root

respectively. This procedure will be applied to each sub-tree of the tree

recursively.

 Algorithm:

If there is a left child, visit it

If there is a right visit it

19 06/04/2022
 Binary Search Trees (BSTs)

 Pre order traversal:

Traverse the root first then traverse into the left sub-tree and right sub-tree
respectively. This procedure will be applied to each sub-tree of the tree recursively.
 Algorithm:

Visit the node itself

If there is a left child, visit it

If there is a right visit it

20 06/04/2022
 Binary Search Trees (BSTs)

 Insert algorithm

If value we want to insert < key of the node, we have to go to the left sub-tree

Otherwise we have to go to the right sub-tree

If current node is empty create a new node with value we are inserting and place

it there as the root

21 06/04/2022
 Binary Search Trees (BSTs)
Inserting 10 into the BST

22 06/04/2022
 Binary Search Trees : Deletion

Delete algorithm

How can we delete a node from BST?

Similar to the insert function, after deletion of a node, the property of the BST

must be maintained

23 06/04/2022
 Binary Search Trees : Deletion
Delete algorithm

How can we delete a node from BST?

Similar to the insert function, after deletion of a node, the property of the BST

must be maintained

24 06/04/2022
 Binary Search Trees : Deletion
 There are 3 possible cases

 Node to be deleted has no children

 We can just delete the node

 Node to be deleted has only one child

 Replace the node with its child and make the parent of the deleted node to be the parent

of the child of the deleted node

 Node to be deleted has two children

 Find the minimum value of right sub-tree

 Delete minimum node of right sub-tree but keep its value

 Replace the value of the node to be deleted by the minimum value whose node was

25 deleted earlier 06/04/2022

 Binary Search Trees (BSTs)
Node to be deleted has two children

26 06/04/2022
 Binary Search Trees (BSTs)
Node to be deleted has no children

27 06/04/2022
 Binary Search Trees (BSTs)
Node to be deleted has only one child

28 06/04/2022
 Binary Search Trees (BSTs)

Minimum number of nodes in a binary tree whose height is h

At least one node at each of first h levels

Minimum number of nodes is h

29 06/04/2022
 Binary Search Trees (BSTs)

• Maximum number of nodes

• All possible nodes at first h levels are present

• Maximum number of nodes

• Maximum possible nodes at level h : 2^h

30 06/04/2022
 Complexity Analysis : Binary Tree
 Searching: For searching element 2, we have to traverse all elements

(assuming we do breadth first traversal). Therefore, searching in binary tree has

worst case complexity of O(n).

 Insertion: For inserting element as left child of 2, we have to traverse all

elements. Therefore, insertion in binary tree has worst case complexity of O(n).

 Deletion: For deletion of element 2, we have to traverse all elements to find 2

(assuming we do breadth first traversal). Therefore, deletion in binary tree has

worst case complexity of O(n)

31 06/04/2022
 Complexity Analysis : BST
Searching: For searching element 1, have to traverse all
elements (in order 3, 2, 1). Therefore, searching in binary
search tree has worst case complexity of O(n). In general, time
complexity is O(h) where h is height of BST.
Insertion: For inserting element 0, it must be inserted as left
child of 1. Therefore, we need to traverse all elements (in order
3, 2, 1) to insert 0 which has worst case complexity of O(n). In
general, time complexity is O(h).
Deletion: For deletion of element 1, we have to traverse all
elements to find 1 (in order 3, 2, 1). Therefore, deletion in
binary tree has worst case complexity of O(n). In general, time
32 06/04/2022
complexity is O(h).
 Full Binary Tree

A full binary tree (sometimes proper binary tree or 2-tree) is a tree in

which every node other than the leaves has two children. 
A full binary tree of a given height h has 2 ^ h -1 nodes

Height 3 full binary tree

33 06/04/2022
 Numbering nodes in a full binary tree
1
 Number nodes 1 through 2^h-1

 Number by levels from top to bottom.

2 3
 Within a level number from left to right.

 Parent of the node i is node i/2, unless i =1

4 5 6 7

 Node 1 is the root and has no parent

 Left child of node i is node 2i, unless 2i>n, where n is the number of nodes

 If 2i>n, node i has no left child

34 06/04/2022
 Node number properties : contd.

 Right child of node i is,

1

 Node 2i+1, unless 2i+1>n, where n is

2 3
the number of nodes
4 5 6 7
 If 2i+1 >n, node I has no right child

35 06/04/2022
 Complete Binary Tree with n Nodes

 Start with a full binary tree that has at least

1
n nodes
 A Binary Tree is complete Binary Tree if 2 3

all levels are completely filled except

4 5 6 7
possibly the last level and the last level has
all keys as left as possible 8

 Complete binary tree with 8 nodes is given

here.
36 06/04/2022
 Binary Tree representation

Array based Representation

Linked Representation

37 06/04/2022
 Array Representation

Number the nodes using the numbering scheme for a full binary tree.

The node that is numbered i is stored in tree[i]

1 a

2 b 3 c

4 d 5 e 6 f 7 g

h i j a b c d e f g h i j
38 8 9 10 0 06/04/2022
10
 Right- Skewed Binary Tree

An n node binary tree needs an array whose length is between n+1
and 2^n
1
a

3
b

7
c

a - b - - - c - - - - - - - d d 15

39 06/04/2022
 Linked Representation

Each binary tree node has a left pointer, right pointer and data field

The space required by an n node binary tree is n*(space required by one

node)

40 06/04/2022
 Linked Representation

root a

b c

d e

f g

41 06/04/2022
 Implementation

42 06/04/2022
 END

43 06/04/2022