Tree Data Structure is a non-linear data
structure in which a collection of elements known as nodes are connected
to each other via edges such that there exists exactly one path between any two
nodes.
A tree data structure is a hierarchical
structure that is used to represent and organize data in a way that is easy to
navigate and search. It is a collection of nodes that are connected by edges
and has a hierarchical relationship between the nodes.
The topmost node of the tree is called the root, and the
nodes below it are called the child nodes. Each node can have multiple child
nodes, and these child nodes can also have their own child nodes, forming a
recursive structure.
Terminologies In Tree Data Structure
- Parent Node: The
node which is a predecessor of a node is called the parent node of that
node. {B} is the parent node of {D, E}.
- Child Node: The
node which is the immediate successor of a node is called the child node
of that node. Examples: {D, E} are the child nodes
of {B}.
- Root Node: The
topmost node of a tree or the node which does not have any parent node is
called the root node. {A} is the root node of the tree. A
non-empty tree must contain exactly one root node and exactly one path
from the root to all other nodes of the tree.
- Leaf Node or
External Node: The nodes which do not have any child nodes are
called leaf nodes. {I, J, K, F, G, H} are the leaf nodes
of the tree.
- Ancestor of a
Node: Any predecessor nodes on the path of the root to that node
are called Ancestors of that node. {A,B} are the ancestor
nodes of the node {E}
- Descendant: A
node x is a descendant of another node y if and only if y is an ancestor
of x.
- Sibling: Children
of the same parent node are called siblings. {D,E} are
called siblings.
- Level of a node: The
count of edges on the path from the root node to that node. The root node
has level 0.
- Internal node: A
node with at least one child is called Internal Node.
- Neighbor of a
Node: Parent or child nodes of that node are called neighbors of
that node.
- Subtree: Any
node of the tree along with its descendant.
- Degree Degree
of a node is equal to the number of children that a node has.
The degree
of a leaf node is zero.
In-degree In-degree
of a node is the number of edges arriving at that node.
Out-degree Out-degree
of a node is the number of edges leaving that node.
TYPES OF
TREES
Trees are of
following 6 types:
1. General
trees
2. Forests
3. Binary
trees
4. Binary
search trees
5.
Expression trees
6.
Tournament trees
Binary trees:
A binary tree is a data structure that is defined as a collection of
elements called nodes. In a binary tree, the topmost element is called the root
node, and each node has 0, 1, or at the most 2 children. A node that has zero
children is called a leaf node or a terminal node. Every node contains a data element,
a left pointer which points to the left child, and a right pointer which points
to the right child. The root element is pointed by a 'root' pointer. If root =
NULL, then it means the tree is empty.
In above Figure shows a binary tree. In the figure, R is
the root node and the two trees T1 and T2 are
called the left and right sub-trees of R. T1
is said to be the left successor of R.
Likewise, T2 is
called the right successor of R.
Note that the left sub-tree of the root node consists of the
nodes: 2, 4, 5, 8, and 9. Similarly, the right sub-tree of the root node
consists of nodes: 3, 6, 7, 10, 11, and 12.
In the tree, root node 1 has two successors: 2 and 3. Node 2
has two successor nodes: 4 and 5. Node 4 has two successors: 8 and 9. Node 5 has
no successor. Node 3 has two successor nodes: 6 and 7. Node 6 has two
successors: 10 and 11. Finally, node 7 has only one successor: 12.
A binary tree is recursive by definition as every node in
the tree contains a left sub-tree and a right sub-tree. Even the terminal nodes
contain an empty left sub-tree and an empty right sub-tree. Look at
Fig above , nodes 5, 8, 9, 10, 11, and 12 have no successors and thus said to
have empty sub-trees.
Terminology
Parent If N is any node in T that has left successor S1
and right successor S2, then N is called the parent of S1 and S2.
Correspondingly, S1 and S2 are called the left child and the right child of N.
Every node other than the root node has a parent.
Level number Every node in the binary tree is assigned a
level number (refer Fig. below). The root node is defined to be at level
0. The left and the right child of the root node have a level number 1. Similarly,
every node is at one level higher than its parents. So all child nodes are
defined to have level number as parent's level number + 1.
Path A sequence of consecutive edges. For example, in Fig. above, the path from the root node to the node 8 is given as: 1, 2, 4, and 8.
Degree of a node It is equal to the number of children
that a node has. The degree of a leaf node is zero. For example, in the tree,
degree of node 4 is 2, degree of node 5 is zero and degree of node 7 is 1.
Sibling All nodes that are at the same level and share
the same parent are called siblings (brothers). For example, nodes 2 and
3; nodes 4 and 5; nodes 6 and 7; nodes 8 and 9; and nodes 10 and 11 are
siblings.
Leaf node A node that has no children is called a leaf
node or a terminal node. The leaf nodes in the tree are: 8, 9, 5, 10, 11, and
12.
Similar binary trees Two binary trees T and T ' are said
to be similar if both these trees have the same structure. Figure shows two
similar binary trees.
Copies Two binary trees T and T ' are said to be copies
if they have similar structure and if they have same content at the
corresponding nodes. Figure below shows that T ' is a copy of T.
Edge It is the line connecting a node N to any of its
successors. A binary tree of n nodes has exactly n – 1 edges because every node
except the root node is connected to its parent via an edge.
Depth The depth of a node N is given as the
length of the path from the root R to the node N. The depth of the root node is
zero.
Height of a tree It is the total number of nodes on the
path from the root node to the deepest node in the tree. A tree with only a
root node has a height of 1.
1. Properties of Binary Tree
·
At each level of
i, the maximum number of nodes is 2i.
·
The height of the
tree is defined as the longest path from the root node to the leaf node. The
tree which is shown above has a height equal to 3. Therefore, the maximum
number of nodes at height 3 is equal to (1+2+4+8) = 15. In general, the maximum
number of nodes possible at height h is (20 + 21 + 22+….2h) = 2h+1 -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.
If there are 'n' number of nodes in the binary tree.
The minimum height can be computed as:
As we know that,
n = 2h+1 -1
n+1 = 2h+1
Taking log on both the sides, log2(n+1) = log2(2h+1)
log2(n+1) = h+1
h = log2(n+1) –
1
The maximum height can be computed as:
As we know that,
n = h+1
h= n-1
In-degree/out-degree of a node It is the number of edges
arriving at a node. The root node is the only node that has an in-degree equal
to zero. Similarly, out-degree of a node is the number of edges leaving
that node.
Binary trees are commonly used to implement binary search trees,
expression trees, tournament trees, and binary heaps.
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.
Let's look at the
simple example of the Full Binary tree.
In the above tree, we
can observe that each node is either containing zero or two children;
therefore, it is a Full Binary tree.
Properties of Full
Binary Tree
The number of leaf
nodes is equal to the number of internal nodes plus 1. In the above example,
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. o 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
Complete Binary Trees
- A complete binary tree is a binary tree that satisfies two properties.
First, in a complete binary tree, every level, except possibly the last, is
completely filled.
- Second, all nodes appear as far left as possible. In a
complete binary tree, the nodes should be added from the left.
The above tree is a complete binary tree because all the nodes are
completely filled, and all the nodes in the last level are added at the left
first.
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.
Representation of Binary Tree
Linked representation of binary trees In the linked
representation of a binary tree, every node will have three parts: the data
element, a pointer to the left node, and a pointer to the right node.
So in C, the binary tree is built with a node type given below.
struct node {
struct node *left;
int data;
struct node *right;
};
linked representation of binary tree
Each node in a Binary Tree has three parts:
- Data
- Pointer to the left child
- Pointer to the right child
Syntax to declare a Node of Binary Tree
// Structure of each node of the tree.
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* newNode(int item) {
struct Node* temp =
(struct Node*)malloc(sizeof(struct Node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
Sequential representation of binary trees
Sequential representation of
trees is done using single or one-dimensional arrays. Though it is the simplest
technique for memory representation, it is inefficient as it requires a lot of memory space.
Binary tree and its sequential representation
**************************************
TRAVERSING
A BINARY TREE
Traversal is a common operation performed on data structures. It is the process in which each and every element present in a data structure is "visited" (or accessed) at least once. This may be done to display all of the elements or to perform an operation on all of the elements.
Tree
Traversal refers to the process of visiting or accessing each node of the tree
exactly once in a certain order. Tree traversal algorithms help us to visit and
process all the nodes of the tree. Since tree is not a linear data structure,
there are multiple nodes which we can visit after visiting a certain node.
There are multiple tree traversal techniques which decide the order in which
the nodes of the tree are to be visited.
Tree
Traversal Techniques:
A Tree
Data Structure can be traversed in following ways:
- Depth First Search or DFS
- Level Order Traversal or
Breadth First Search or BFS
Inorder
Traversal:
Inorder traversal visits the node in the
order:
Left -> Root -> Right
Algorithm for
Inorder Traversal:
Inorder(tree)
- Traverse the left subtree,
i.e., call Inorder(left->subtree)
- Traverse the right subtree,
i.e., call Inorder(right->subtree)
Uses of Inorder Traversal:
- In
the case of binary search trees (BST), Inorder traversal gives nodes in
non-decreasing order.
- To
get nodes of BST in non-increasing order, a variation of Inorder traversal
where Inorder traversal is reversed can be used.
- Inorder
traversal can be used to evaluate arithmetic expressions stored in
expression trees.
******************************
Preorder
Traversal:
Preorder traversal visits the node in
the order:
Root -> Left -> Right
Algorithm
for Preorder Traversal:
Preorder(tree)
- Traverse the left subtree,
i.e., call Preorder(left->subtree)
- Traverse the right subtree,
i.e., call Preorder(right->subtree)
Uses of Preorder Traversal:
- Preorder
traversal is used to create a copy of the tree.
- Preorder
traversal is also used to get prefix expressions on an expression tree.
***********************************************
Postorder
Traversal:
Postorder traversal visits the node in
the order:
Left -> Right -> Root
Algorithm for Postorder Traversal:
Algorithm Postorder(tree)
- Traverse
the left subtree, i.e., call Postorder(left->subtree)
- Traverse
the right subtree, i.e., call Postorder(right->subtree)
Uses of Postorder Traversal:
- Postorder
traversal is used to delete the tree.
- Postorder
traversal is also useful to get the postfix expression of an expression
tree.
- Postorder
traversal can help in garbage collection algorithms, particularly in
systems where manual memory management is used.
************************************
Level Order
Traversal :
Level Order Traversal visits all
nodes present in the same level completely before visiting the next level.
Algorithm for Level Order Traversal:
LevelOrder(tree)
- Enqueue
the root node of the tree to Q
- Loop
while Q is not empty
- Dequeue
a node from Q and visit it
- Enqueue
the left child of the dequeued node if it exists
- Enqueue
the right child of the dequeued node if it exists
Printing the value of each node as we "visit" it, we get the following output level order
A B W X S T C E M P N H
Uses of Level Order:
- Level Order Traversal is mainly used as Breadth First Search to search or process nodes level-by-level.
- Level Order traversal is also used for Tree Serialization and Deserialization .
