Data Structures &
Algorithm Design
Trees
L.Mais Saad Safoq
Computer Science Department
Karballa University
2020
10-1
Tree Definition
• Tree: a set of elements of the same type
such that
• it has a distinguished element called the root
from which descend zero or more trees
(subtrees)
• Examples in real life:
• Family tree
• Table of contents of a book
10-2
Tree Terminology
• Nodes: the elements in the tree
• Edges: connections between nodes
• Root: the distinguished element that is the
origin of the tree
• There is only one root node in a tree
• Leaf node: a node without an edge to another
node
• Interior node: a node that is not a leaf node
• Empty tree has no nodes and no edges
10-3
Tree Terminology
• Parent or predecessor: the node directly
above in the hierarchy
• A node can have only one parent
• Child or successor: a node directly below in
the hierarchy
• Ancestors of a node: its parent, the parent of
its parent, etc.
• Descendants of a node: its children, the
children of its children, etc.
10-4
Tree Terminology
• Subtree of a node: consists of a child node and
all its descendants
• A subtree is itself a tree
• A node may have many subtrees
• If A is the root of a binary tree and B is the root
of its left or right subtrees, then A is said to be
the father of B and B is said to be the
left/right son of A.
• Two nodes are brothers if they are left and
right sons of the same father.
10-5
Tree Terminology
Root
Subtrees of
the root
10-6
Subtrees
Subtrees of the
node labeled E
10-7
Tree Terminology
Root
Interior
nodes
Leaf
nodes
10-8
Height of a Tree
• A path is a sequence of edges leading from one
node to another
• Length of a path: number of edges on the
path
• Height of a (non-empty) tree : length of the
longest path from the root to a leaf
(maximum level of any node)
• What is the height of a tree that has only a
root node?
• By convention, the height of an empty tree
is -1
10-9
Level and Degree of a Node
• Level of a node : number of edges between
root and node
• Level of root node is 0
• Level of a node that is not the root node
is level of its parent + 1
• Degree of a node: the number of children it
has
• Degree of a tree: the maximum of the
degrees of the tree’s nodes
10-10
Level of a Node
Level 0
Level 1
Level 2
Level 3
10-11
Binary Trees
• General tree: a tree each of whose nodes
may have any number of children
• n-ary tree: a tree each of whose nodes may
have no more than n children
• Binary tree: a tree each of whose nodes
may have no more than 2 children
• a binary tree is a tree with degree 2
10-12
Binary Trees
Tree with 0–2 children per node
The children (if present) are called
the left child and right child
a tree where every node has left and
right subtrees is a binary tree
10-13
Binary Trees
Strictly Binary Tree
All non-leaf nodes have two branches
Complete Binary Tree
All its leaf nodes at the same level
Almost Complete Binary Tree
The last level is partially filled from
left to right.
10-14
Binary Trees
A
B C
D E F G
H I J K
•Not Complete BT, Strictly BT, Almost complete BT
10-15
Binary Tree Properties
The number of nodes n in a complete
binary tree is at least n = 2h and at most
n = 2(h + 1) − 1 where h is the height of the
tree.
The number of leaf nodes L in a complete
binary tree can be found using this
formula: L = 2h where h is the height of the
tree.
The number of nodes n in a perfect binary
tree can also be found using this formula:
n = 2L − 1 where L is the number of leaf
nodes in the tree.
16
Binary Search Tree
Binary Search Tree is a binary tree
in which nodes are arranged
according to their values.
The left node has a value less than its
parent
The right node has a values greater
than its parent
10-17
Binary Search Tree Construction
How to build & maintain binary
trees?
Insertion
Deletion
Maintain key property
Smaller values in left subtree
Larger values in right subtree
10-18
Declaration BT
A node consists of three fields such as :
• Left Child (LChild)
• Information of the Node (Info)
• Right Child (RChild)
struct node {
int info;
struct node *left;
struct node *right;
};
19
Binary Search Tree – Insertion
1. Perform comparison for value X
2. Comparison will end at node Y (if X not in
tree)
3. If X < Y, insert new leaf X as new left
subtree for Y
4. If X > Y, insert new leaf X as new right
subtree for Y
10-20
Insertion- Examples
5
10 10
2 45
5 30 5 45
30
2 25 45 2 25 30
10
25
Binary search Not a binary
trees search tree
10-21
Insertion- Example
Insert ( 20 )
10 20 >10, right
20 < 30, left
5 30
20 < 25, left
2 25 45 Insert 20 as left leaf
20
10-22
Binary Search Tree
Given the following sequence of numbers,
14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5
The following binary search tree can be constructed.
14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5 and 14 is the root
Algorithm for insert node in BST
Steps processing (by Recursion)
1.check if tree not contain any node
if Root = NULL
create node in tree
2.Else
if x< Root Inf
Add the new value in the left subtree
Rootleft = insert(Rootleft, x);
3.Else
Add the new value in the right subtree
Rootright = insert(Rootright, x);
25
Insertion of node in BST
node * Insert(node *p, int x)
{
if(p==NULL) {
p=make(x);
return p; }
else {
if(x<p->inf)
p->left=Insert(p->left, x);
else
p->right=Insert(p->right,x);
return p;
}}
10-26
Traversing :
Means visiting all the nodes of the tree, in
some specific order for processing.
There are THREE ways of Traversing a
Tree
1. Preoder Traversal
2. Inorder Traversal
3. Postorder Traversal
4. Levelorder Traversal
Preorder Traversal Method
Traversing a binary tree in preorder
(Root – Left – Right)
1. Visit the root.
2. Traverse the left subtree in
preorder.
3. Traverse the right subtree in
preorder.
Preorder Traversal Method
void PreOrder(node *&h)
{
if (h!=NULL)
{
cout<<h->inf;
PreOrder(h->left);
PreOrder(h->right);
}}
10-30
Inorder Traversal Method
Traversing a binary tree in inorder
(Left – Root – Right)
1. Traverse the left subtree in
inorder.
2. Visit the root.
3. Traverse the right subtree in
inorder
Inorder Traversal Method
int InOrder(node *&h)
{
if (h!=NULL)
{
InOrder(h->left);
cout<<h->inf;
InOrder(h->right);
}}
10-32
Postorder Traversal Method
Traversing a binary tree in postorder
(Left – Right – Root)
1. Traverse the left subtree in
postorder.
2. Traverse the right subtree in
postorder.
3. Visit the root postorder
Postorder Traversal Method
int PostOrder(node *&h)
{
if (h!=NULL)
{
PostOrder(h->left);
PostOrder(h->right);
cout<<h->inf;
}}
10-36
Levelorder Traversal Method
levelorder Example (Visit = print)
Travers tree level by level
Traversals: Example
