Chapter Five

Trees
Tree
• A tree is also one of the data
structures that represent
hierarchical data.
• Suppose we want to show the
employees and their positions in
the hierarchical form then it can
be represented as shown below:
•
Some key points of the Tree data structure
1. A tree data structure is defined as a collection of objects or entities
known as nodes that are linked together to represent or simulate
hierarchy.
2. A tree data structure is a non-linear data structure because it does not
store in a sequential manner. It is a hierarchical structure as elements in
a Tree are arranged in multiple levels.
3. In the Tree data structure, the topmost node is known as a root node.
Each node contains some data, and data can be of any type. In the
above tree structure, the node contains the name of the employee, so
the type of data would be a string.
4. Each node contains some data and the link or reference of other nodes
that can be called children.
Some basic terms used in Tree data structure
• Root: The root node is the topmost node in the tree
hierarchy. In other words, the root node is the one
that doesn't have any parent. In the above structure,
node numbered 1 is the root node of the tree. If a
node is directly linked to some other node, it would be
called a parent-child relationship.
• Child node: If the node is a descendant of any node,
then the node is known as a child node.
• Parent: If the node contains any sub-node, then that
node is said to be the parent of that sub-node.
• Sibling: The nodes that have the same parent are
known as siblings.
Some basic terms used in Tree data structure
• Leaf Node:- The node of the tree, which doesn't have
any child node, is called a leaf node. A 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.
• Internal nodes: A node has atleast one child node
known as an internal
• Ancestor node:- An ancestor of a node is any
predecessor node on a path from the root to that
node. The root node doesn't have any ancestors. In
the tree shown in the above image, nodes 1, 2, and 5
are the ancestors of node 10.
• Descendant: The immediate successor of the given
node is known as a descendant of a node. In the above
figure, 10 is the descendant of node 5.
Properties of Tree data structure
• Number of edges: If there are n nodes, then there would n-1 edges. Each arrow
in the structure represents the link or path. Each node, except the root node, will
have atleast one incoming link known as an edge. There would be one link for the
parent-child relationship.
• Depth of node x: The depth of node x can be defined as the length of the path
from the root to the node x. One edge contributes one-unit length in the path.
So, the depth of node x can also be defined as the number of edges between the
root node and the node x. The root node has 0 depth.
• Height of node x: The height of node x can be defined as the longest path from
the node x to the leaf node.
Implementation of Tree
• The tree data structure can be created
by creating the nodes dynamically
with the help of the pointers.
• The tree in the memory can be
represented a
• The node contains three fields.
• The second field stores the data;
• the first field stores the address of the
left child, and
• the third field stores the address of the
right childs in the figure.
Implementation of Tree
• In programming, the structure of a node can be
defined as shown in the figure.
• The above structure can only be defined for the
binary trees because the binary tree can have utmost
two children, and generic trees can have more than
two children.
• The structure of the node for generic trees would be
different as compared to the binary tree.
•
Applications of trees
• Storing naturally hierarchical data: Trees are used to store the data in the
hierarchical structure. For example, the file system. The file system stored on
the disc drive, the file and folder are in the form of the naturally hierarchical
data and stored in the form of trees.
• Organize data: It is used to organize data for efficient insertion, deletion and
searching. For example, a binary tree has a logN time for searching an
element.
• Trie: It is a special kind of tree that is used to store the dictionary. It is a fast
and efficient way for dynamic spell checking.
• Heap: It is also a tree data structure implemented using arrays. It is used to
implement priority queues.
• B-Tree and B+Tree: B-Tree and B+Tree are the tree data structures used to
implement indexing in databases.
• Routing table: The tree data structure is also used to store the data in routing
tables in the routers.
Types of Tree data structure
General tree
• The general tree is one of the types of tree data
structure. In the general tree, a node can have
either 0 or maximum n number of nodes.
• There is no restriction imposed on the degree of
the node (the number of nodes that a node can
contain).
• The topmost node in a general tree is known as
a root node.
• The children of the parent node are known
as subtrees.
• Every non-empty tree has a downward edge,
and these edges are connected to the nodes
known as child nodes.
• The root node is labeled with level 0. The nodes
that have the same parent are known
as siblings.
Types of Tree data structure

Binary tree
• Here, binary name itself suggests two
numbers, i.e., 0 and 1.
• In a binary tree, each node in a tree can have
utmost two child nodes.
• Here, utmost means whether the node has 0
nodes, 1 node or 2 nodes.
Types of Tree data structure (cont …)

Binary Search Tree

• Binary search tree is a non-linear data structure in which one
node is connected to n number of nodes.
• A node can be represented in a binary search tree with three
fields, i.e., data part, left-child, and right-child.
• A node can be connected to the utmost two child nodes in a
binary search tree, so the node contains two pointers (left
child and right child pointer).
• Every node in the left subtree must contain a value less than
the value of the root node, and the value of each node in the
right subtree must be bigger than the value of the root node.
Types of Tree data structure (cont …)
AVL Tree
• It is one of the types of the binary tree invented
by Adelson Velsky Lindas.
• AVL tree satisfies the property of the binary tree as well as
of the binary search tree.
• It is a self-balancing tree which means that balancing the
heights of left subtree and right subtree.
• This balancing is measured in terms of the balancing factor.
• We can consider a tree as an AVL tree if the tree obeys the
binary search tree as well as a balancing factor.
• The balancing factor can be defined as the difference
between the height of the left subtree and the height of
the right subtree.
• The balancing factor's value must be either 0, -1, or 1;
therefore, each node in the AVL tree should have the value
of the balancing factor either as 0, -1, or 1.
Binary Tree
• The Binary tree means that the node • The logical representation of the
can have maximum two children. given tree is given below:
Properties of Binary Tree

1. At each level of i, the maximum number of nodes is 2i.

2. The height of the tree is defined as the longest path from the root
node to the leaf node. In general, the maximum number of nodes
possible at height h is (20 + 21 + 22+….2h) = 2h+1 -1.
3. The minimum number of nodes possible at height h is equal to h+1.
4. 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.
Types of Binary Tree

• There are four types of Binary tree:

1. Full/ proper/ strict Binary tree

2. Complete Binary tree

3. Perfect Binary tree

4. Degenerate Binary tree

5. Balanced Binary tree

1. Full/ proper/ strict Binary tree
• The full binary tree is also known as a
strict binary tree.

• The tree can only be considered as the

full binary tree if each node must
contain either 0 or 2 children.

• The full binary tree can also be

defined as the tree in which each
node must contain 2 children except
the leaf nodes.
2. Complete Binary Tree
• The complete binary tree is a tree in
which all the nodes are completely
filled except the last level.

• In the last level, all the nodes must be

as left as possible. In a complete
binary tree, the nodes should be
added from the left.
• Let's create a complete binary tree.
3. Perfect Binary Tree
• A tree is a perfect binary tree
• if all the internal nodes have 2 children,
and
• all the leaf nodes are at the same level.

Not Perfect Binary Tree

Perfect Binary Tree
4. Degenerate Binary Tree
• The degenerate binary tree is a tree in which • Degenerate binary tree + left-skewed
all the internal nodes have only one children. tree as all the nodes have a left child
• Degenerate Binary Tree + Right-skewed tree only.
as all the nodes have a right child only
Balanced Binary Tree
• The balanced binary tree is a tree in
which both the left and right trees
height differ by atmost 1.
• For example, AVL and Red-Black
trees are balanced binary tree.
•

Not balanced tree

Binary Tree Implementation
• A Binary tree is implemented • In this structure, data is the value, left
with the help of pointers. pointer contains the address of the left
node, and right pointer contains the address
• The first node in the tree is of the right node.
represented by the root
pointer.
• Each node in the tree consists
of three parts, i.e., data, left
pointer and right pointer.
• To create a binary tree, we
first need to create the node.
 Array Representation for Tree
• The binary tree can be represented using • The array representation of the binary tree
an array of size 2n+1 if the depth of the is :
binary tree is n. As in the above binary tree, A was the root node, so
• If the parent element is at the index p, that it will be stored in the 0th index.
Then the left child will be stored in the • The left child of A will be stored in the 2(0)+1 equal
index (2p)+1, (2p)+1, and the right child to the 1st location.
will be stored in the index (2p)+2, (2p)+2 • So, B is stored in index 1. And similarly, the right
child of A will be stored in the 2(0)+2 index.
• For every node, the left and right child will be stored
accordingly.
Linked List Representation of Tree
• For the linked list representation, we will
use the doubly linked list, which has two
pointers so that we can point to the left
and right children of a binary tree node.
• NULL is given to the pointer as the address
when no child is connected.
Declaration of a Binary Tree in C
• To declare the nodes of the binary • Create a New Node of the Binary Tree in C
tree, we will create a structure • To create a new node of the binary tree,
containing one data element and two we will create a new function that will take
pointers of the name left and right. the value and return the pointer to the
• new node created with that value.
• The new node which is being created will have
the left and right pointers, pointing at null.
•
Inserting the Left and/or the Right Child of a Node
• This function will take two inputs, first the
value that needs to be inserted and second
the node's pointer on which the left or the
right child will be attached.
• To insert into the left side of the root node,
we will simply call the create function with
the value of the node as a parameter.
• So that a new node will be created, and as
that function returns a pointer to the newly
created node, we will assign that pointer to
the left pointer of the root node that is
being taken as input.
• Similarly, insertion on the right side will call
the create function with the given value,
and the returned pointer will be assigned to
the write pointer of the root node.
Traversal of Binary Tree
• We can traverse the element tree • Pre-order
and can display these elements in
three formats/methods : • In this type of traversal, first, we will take
the value of the current node(present
• In every traversal method of the node), then we will go to the left node, and
binary tree, we need to visit the left after that, we will go to the right node.
node, the right node, and the data of
the present/current node(root). •
• Three methods will have these three
actions in a different order.
• Pre-order
• In-order
• Post-order
Traversal of Binary Tree (cont …)
• In-Order • Post-Order
In this type of traversal, first, we'll go In this type of traversal, first, we'll go to the
to the left node, then we'll take the left node, then to the right node, and at
value of the current node, and then last, we will take the current node's value.
we will go to the right node.
Traversal of Binary Tree (cont …)
Binary Search tree
• A binary search tree follows some
order to arrange the elements. In a
Binary search tree, the value of left
node must be smaller than the parent
node, and the value of right node
must be greater than the parent node.
• This rule is applied recursively to the
left and right subtrees of the root.
• Let's understand the concept of Binary
search tree with an example.
Example of creating a binary search tree
• Now, let's see the creation of binary search tree using an example.
• Suppose the data elements are - 45, 15, 79, 90, 10, 55, 12, 20, 50
•
Example of creating a binary search tree
• Now, let's see the creation of binary search tree using an example.
• Suppose the data elements are - 45, 15, 79, 90, 10, 55, 12, 20, 50
•
Example of creating a binary search tree