DATA STRUCTURES

Trees
Trees
◻ The linear access time of lists makes them prohibitive
for large input sets.
Solution is to use non linear data structures, e.g. Trees.
◻ A tree is often used to represent a hierarchy .
◻ Because the relationships between the items in the
hierarchy suggest the branches of a botanical tree.
◻ For example, a tree-like organization chart is often
used to represent the lines of responsibility in a
business.
Organizational Chart
 Trees

◻ As we see in the figure, the tree is upside-down.

◻ This is the usual way the data structure is drawn.
◻ The president is called the root of the tree and the clerks are the
leaves.
Tree Formal Definitions
◻ A tree is a collection of nodes. The collection can
be empty,
◻ Otherwise, a tree consists of a distinguished node
r, called the root, and zero or more (sub) trees T1,
T2,.……, Tk, each of whose roots are connected by
a directed edge to r.
◻ The root of each subtree is said to be a child of r
and r is the parent of each subtree root.
Tree Formal Definitions

B C D E F G

H I J K L M N

P Q

A Tree
 Tree Formal Definitions
◻ A tree is a collection of n nodes, one of which is the root, and n -1
edges.
n -1 edges, because each edge connects some node to its parent, and every
node except the root has one parent.
◻ Each node may have an arbitrary number of children, possibly zero.
Nodes with no children are known as leaves.
Nodes with the same parent are siblings.
◻ A Path from node n1 to nk is defined as a sequence of nodes n1, n2,
…,nk such that ni is the parent of ni + 1.
◻ The length of this path is the number of edges on the path.
◻ There is a path of length zero from every node to itself.
◻ In a tree, there is exactly one path from the root to each node.
 Tree Formal Definitions
◻ For any node ni, the depth of ni is the unique path from the
root to ni. Thus the root is at depth 0.
◻ The height of ni is the longest path from ni to a leaf. Thus
all leaves are at height 0.
◻ The height of the tree is equal to the height of the root.
◻ The depth of a tree is equal to the depth of the deepest
leaf. This is always equals to the height of the tree.
◻ If there is a path from n1 to n2, then n1 is ancestor of n2 and
n2 is a descendant of n1. If n1 ≠ n2, then n1 is a proper
ancestor of n2 and n2 is a proper descendent of n1.
Types of Trees
◻ Binary Tree
◻ Binary Search Tree
◻ AVL Tree
◻ B-Tree
 Binary Tree
◻ The simplest form of tree is a binary tree. A Binary tree is
a collection of nodes. The collection can be empty.
Otherwise a binary tree consists of
a node (called the root node) and
left and right sub-trees.
Both the sub-trees are themselves binary trees
◻ We now have a recursively defined data structure.
Binary Tree
root

B C

D E F

G H I

Left subtree Right subtree

Binary Tree
◻ Recursive definition
A
root

B C

D E F

Left subtree G H I

Right subtree
Cont…
◻ A binary tree is a finite set of elements that is
either empty or is partitioned into three
disjoint subsets.
◻ The first subset contains a single element
called the root of the tree.
◻ The other two subsets are themselves binary
trees called the left and right subtrees.
◻ Each element of a binary tree is called a node
of the tree.
Binary Tree Characteristics
◻ The root of each subtree is a child of r
◻ r is the parent of each subtree root

TR
TL
Binary Tree
Not a Tree
◻ Structures that are not trees.

B C

D E F

G H I
Not a Tree
◻ Structures that are not trees.

B C

D E F

G H I
Not a Tree
◻ Structures that are not trees.

B C

D E F

G H I
Notation
node
A
root•
left subtree• B C
right subtree•

D E F

G H I

It consists of a root and two subtrees

 Notation

B C

D E F

G H I
– edge
there is an edge from the root to its children
Notation

children
B C

D E F

G H I
 Notation

children
B C

?Who are node C’s children D E F

G H I

?Who are node A’s children

 Notation

descendants
B C

?Who are node C’s descendants D E F

G H I

?Who are node A’s descendants

 Notation

parents
B C

?Who is node E’s parent D E F

G H I

?Who is node H’s parent

 Notation

ancestors
B C

?Who are node D’s ancestors D E F

G H I

?Who are node H’s ancestors

Notation

from J to A
A

B C
– path
If n1, n2,…nk is a sequence D E F
of nodes such that ni is the
parent of ni+1, then that
.sequence is a path
G H I

.The length of the path is k-1■ J

Level of a Binary Tree Node
◻ The level of a node in a binary tree is defined
as follows:
▪ Root has level 0,
▪ Level of any other node is one more than the level
its parent (father).
◻ The depth of a binary tree is the maximum
level of any leaf in the tree.
Level of a Binary Tree Node

A 0 Level 0

B 1 C 1 Level 1

D 2 E 2 F 2 Level 2

G 3 H 3 I 3 Level 3
Notation

B C

2 D E F

– depth
the length of the path
G H I
from the root of the tree
to the node
Notation

0 A

1 B C

2 D E F

3 G H I
– level
all nodes of depth d are
at level d in the tree
Notation

B C

D E F

– leaf node
any node that has two
G H I
empty children
Notation

B C

D E F

– internal node
any node that has at
G H I
least one non-empty
child
Binary Tree
◻ If every non-leaf node in a binary tree has non-empty left and right
subtrees, the tree is termed a strictly binary tree.

B C

D E J F

G K H I
Complete Binary Tree
◻ A complete binary tree of depth d is the strictly
binary all of whose leaves are at level d.
0
A

B 1 C 1

D 2 E 2 F 2 G 2

H 3 I J 3 K L 3 M 3 N 3 O 3
Binary Trees
Some Binary Trees

One node Two nodes

Three nodes
Dynamic Implementation of Binary Tree
Linked Implementation
 Binary Tree Traversal

◻ Tree Traversal is the process of visiting each node in the

tree exactly one time.
◻ Tree traversals are of two types
Depth First Traversal
Breadth First Traversal
◻ The three Depth First Traversal techniques are
Preorder tree traversal
Inorder tree traversal
Postorder tree traversal
Traversing a Binary Tree
◻ Suppose we have a binary tree, ordered (BST)
or unordered.
◻ We want to print all the values stored in the
nodes of the tree.
◻ In what order should we print them?
Traversing a Binary Tree
◻ Ways to print a 3 node tree:

14

4 15

(4,15,14) ,(15 ,14 ,4)

(14,15,4) ,(14,4,15)
(15,14,4) ,(15,4,14)
Traversing a Binary Tree
◻ In case of the general binary tree:
N node

L left right R
subtree subtree

(L,R,N) ,(L,N,R)
(N,R,L) ,(N,L,R)
(R,N,L) ,(R,L,N)
Traversing a Binary Tree
◻ Three common ways
N node

left right
L subtree subtree R

(N,L,R) Preorder:
(L,N,R) Inorder:
(L,R,N) Postorder:
 Binary Tree Traversal
◻ Preorder Tree Traversal:
1. Visit the root
2. Traverse the left sub-tree in preorder
3. Traverse the right sub-tree in preorder

A
B
:Example C
ABCDE D E
Traversing a Binary Tree
14

4 15

3 9 18

7 16 20

5 17

Preorder: 14 4 3 9 7 5 15 18 16 17 20
Binary Tree Traversal
void preorder(BinaryTreeNode* node) {
if (node != nullptr) {
cout << node->data << " ";
preorder(node->left);
preorder(node->right);
}
}
 Binary Tree Traversal
◻ inorder Tree Traversal:
1. Traverse the left sub-tree in inorder
2. Visit the root
3. Traverse the right sub-tree in inorder

A
B
:Example C

D E
ADCEB
Traversing a Binary Tree
14

4 15

3 9 18

7 16 20

5 17

Inorder: 3 4 5 7 9 14 15 16 17 18 20
Binary Tree Traversal
void inorder(BinaryTreeNode* node) {
if (node != nullptr) {
inorder(node->left);
cout << node->data << " ";
inorder(node->right);
}
}
 Binary Tree Traversal
◻ postorder Tree Traversal:
1. Traverse the left sub-tree in postorder
2. Traverse the right sub-tree in postorder
3. Visit the root

A
B
:Example C
DECBA D E
Traversing a Binary Tree
14

4 15

3 9 18

7 16 20

5 17

Postorder: 3 5 7 9 4 17 16 20 18 15 14
Binary Tree Traversal
void postorder(BinaryTreeNode* node) {
if (node != nullptr) {
postorder(node->left);
postorder(node->right);
cout << node->data << " ";
}
}
Binary Tree Traversal
.Traverse the following tree
1
4 1
4 5
1
3 1
9 8
4 2
1
7 9 0
?Pre-order Traversal 6
?Post-order Traversal 5 1
7
?In-order Traversal 4 5
Preorder Traversal
◻ Preorder traversal
Node – Left – Right
Prefix expression
■ ++a*bc*+*defg
Inorder Traversal
◻ Inorder traversal
left, node, right.
infix expression
■ a+b*c+d*e+f*g
Postorder Traversal
◻ Postorder Traversal
left, right, node
postfix expression
■ abc*+de*f+g*+
Binary Tree Traversals
◻ Depth First Tree Traversal
■ PreOrder Tree Traversal
■ InOrder Tree Traversal
■ PostOrder Tree Traversal
◻ Breadth First Tree Traversal
Also knows as level order traversal
Binary Trees Traversals
◻ Breadth First Tree Traversal
Implementation of this kind of traversal is
straightforward when a queue is used.
Consider a top down left-to-right, breadth
first traversal.
After a node is visited, its children, if any,
are placed at the end (rear) of a queue, and
the node at the beginning (front) of the
queue is visited.
Breadth First Traversal Example

C B

D
E H

F
G
I
Breadth First Traversal Example

A Queue
C B
C B Front Rear

D
E H

F
G
I
A
Breadth First Traversal Example

A Dqueue C
B
C B

D
E H

F
G
I
AC
Breadth First Traversal Example

A Enqueu D
B D
C B

D
E H

F
G
I
AC
Breadth First Traversal Example

A Dqueue B
D
C B

D
E H

F
G
I
ACB
Breadth First Traversal Example

A Enqueue E, H
D E H
C B

D
E H

F
G
I
ACB
Breadth First Traversal Example

A Dqueue D
E H
C B

D
E H

F
G
I
ACBD
Breadth First Traversal Example

A Dqueue E
H
C B

D
E H

F
G
I
ACBDE
Breadth First Traversal Example

A Enqueue F, G
H F G
C B

D
E H

F
G
I
ACBDE
Breadth First Traversal Example

A Dqueue H
F G
C B

D
E H

F
G
I
ACBDEH
Breadth First Traversal Example

A Enqueue I
F G I
C B

D
E H

F
G
I
ACBDEH
Breadth First Traversal Example

A Dqueue F
G I
C B

D
E H

F
G
I
ACBDEHF
Breadth First Traversal Example

A Dqueue G
I
C B

D
E H

F
G
I
ACBDEHFG
Breadth First Traversal Example

A Dqueue I

C B

D
E H

F
G
I
ACBDEHFGI
 Binary Trees Traversals
void breadthFirst()
{
Queue queue;
Node *p = root;

// Check if the tree is not empty

if (p != NULL)
{
queue.enqueue(p); // Enqueue the root node
while (!queue.empty())
{
p = queue.dequeue(); // Dequeue the front node
cout << p->key << " "; // Print the node's value

// Enqueue the left child if it exists

if (p->left != NULL)
queue.enqueue(p->left);

// Enqueue the right child if it exists

if (p->right != NULL)
queue.enqueue(p->right);
} } }