TREE Data Structure
A tree is a nonlinear hierarchical data structure that
consists of nodes connected by edges.
Each node contains a value and may or may not have a
child node.
This data structure is called a Tree because it resembles
a tree. It starts with a root node and branches off with its
descendants. It provides much quicker access to the
data which is non-linear.
Importance of Tree Data Structure
Other data structures such as arrays, linked list, stack,
and queue are linear data structures that store data
sequentially. In order to perform any operation in a linear
data structure, the time complexity increases with the
increase in the data size. But, it is not acceptable in
today's computational world.
Different tree data structures allow quicker and easier
access to the data as it is a non-linear data structure.
Tree Terminologies
1. Node
A node is an entity that contains a key or value and
pointers to its child nodes.
The last nodes of each path are called leaf nodes or
external nodes that do not contain a link/pointer to child
nodes.
The node having at least a child node is called
an internal node.
2. Edge
It is the link between any two nodes.
Tree Terminologies
3. Root
It is the topmost node of a tree.
4. Height of a Node
The height of a node is the number of edges from the
node to the deepest leaf (ie. the longest path from the
node to a leaf node).
5. Depth of a Node
The depth of a node is the number of edges from the
root to the node.
Tree Terminologies
7. Degree of a Node
The degree of a node is the total number of branches of
that node.
8. Forest
A collection of disjoint trees is called a forest. You can
create a forest by cutting the root of a tree.
Creating forest from a tree
BST Basic Operations
The basic operations that can be performed on a binary
search tree data structure, are the following −
•Insert − Inserts an element in a tree/create a tree.
•Search − Searches an element in a tree.
•Preorder Traversal − Traverses a tree in a pre-order
manner.
•Inorder Traversal − Traverses a tree in an in-order
manner.
•Postorder Traversal − Traverses a tree in a post-order
manner.
Tree Applications
•Binary Search Trees(BSTs) are used to quickly check
whether an element is present in a set or not.
•Heap is a kind of tree that is used for heap sort.
•A modified version of a tree called Tries is used in
modern routers to store routing information.
•Most popular databases use B-Trees and T-Trees,
which are variants of the tree structure we learned
above to store their data
•Compilers use a syntax tree to validate the syntax of
every program you write.
Tree Traversal
Traversing a tree means visiting every node in the tree.
You might, for instance, want to add all the values in the
tree or find the largest one. For all these operations, you
will need to visit each node of the tree.
There are three ways to traverse a tree structure
1. Inorder
2. Preorder
3. postorder
Inorder Traversal
In this traversal method, the left subtree is visited first,
then the root and later the right sub-tree. We should
always remember that every node may represent a
subtree itself.
If a binary tree is traversed inorder, the output will
produce sorted key values in an ascending order.
1.First, visit all the nodes in the left subtree
2.Then the root node
3.Visit all the nodes in the right subtree
We start from A, and following in-order traversal, we
move to its left subtree B. B is also traversed in-order.
The process goes on until all the nodes are visited. The
output of inorder traversal of this tree will be −
D→B→E→A→F→C→G
Preorder Traversal
In this traversal method, the root node is visited first,
then the left subtree and finally the right subtree.
We start from A, and
following pre-order
traversal, we first
visit A itself and then move
to its left subtree B. B is
also traversed pre-order.
The process goes on until
all the nodes are visited.
The output of pre-order
traversal of this tree will be
A→B→D→E→C→F→G
1.Visit root node
2.Visit all the nodes in the left subtree
3.Visit all the nodes in the right subtree
Postorder Traversal
In this traversal method, the root node is visited last,
hence the name. First we traverse the left subtree, then
the right subtree and finally the root node.
1.Visit all the nodes in the left subtree
2.Visit all the nodes in the right subtree
3.Visit the root node
We start from A, and
following Post-order
traversal, we first visit the
left subtree B. B is also
traversed post-order. The
process goes on until all the
nodes are visited. The
output of post-order
traversal of this tree will be
D→E→B→F→G→C→A
Types of Trees in Data Structure
1. General Tree
A general tree is a tree data structure where there are
no constraints on the hierarchical structure. A 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.
There can be n number of subtrees in a general tree. In
the general tree, the subtrees are unordered as the
nodes in the subtree cannot be ordered.
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. This means whether the node
has 0 nodes, 1 node or 2 nodes.
Q u e s t i o n
Using the tree below, Show the Inorder, Preorder and
Postorder Tree Traversals
