DS 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
Organizational Hierarchy
CEO
Manager Direct Reports
The root is at the top, and
its branches are moving in
a downward direction.

Direct Reports

Direct Reports

Direct Reports Direct Reports

Key points of the Tree data structure.

•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.

•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.

•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.

•Each node contains some data and the link or reference of other
nodes that can be called children.
root
link
•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.

•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.
Child Node
Parent Node Parent Node

Siblings Parent Siblings

5
Internal Node
s ce n d ant of
h e De
10 is t

Leaf Node
Siblings
Ancestor Node of 10 are 1,2, and 5
Properties of Tree data structure

Recursive data
structure:
The tree is also known as a recursive data
structure. A tree can be defined as
recursively because the distinguished node in
a tree data structure is known as a root
node. The root node of the tree contains a
link to all the roots of its subtrees. The left
subtree is shown in the yellow color in the
below figure, and the right subtree is shown
in the black color. The left subtree can be
further split into subtrees shown in three
different colors. Recursion means reducing
something in a self-similar manner. So, this
recursive property of the tree data structure
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 as
shown below:
Applications of trees
The following are the 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.
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.
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.
Let's understand the binary

Binary tree: Here, binary tree through an example.

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.
Logical Representation
Binary Search tree: Binary
search tree is a non-linear data
structure in which one node is
connected to n number of nodes. It is a
node-based data structure. 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).
Advantages of using binary search tree
1. Searching become very efficient in a binary search tree since,
we get a hint at each step, about which sub-tree contains the
desired element.

2. The binary search tree is considered as efficient data structure

in compare to arrays and linked lists. In searching process, it
removes half sub-tree at every step. Searching for an element in
a binary search tree takes o(log2n) time. In worst case, the time
it takes to search an element is 0(n).

3. It also speed up the insertion and deletion operations as

compare to that in array and linked list.
Q. Create the binary search tree using the
following data elements.
43, 10, 79, 90, 12, 54, 11, 9, 50

1.Insert 43 into the tree as the root of the tree.

2.Read the next element, if it is lesser than the root
node element, insert it as the root of the left sub-
tree.
3.Otherwise, insert it as the root of the right of the
right sub-tree.
The process of creating BST by using the given
43, 10, 79, 90, 12, 54, 11, 9, 50
elements, is shown in the image below.
SN Operation Description
1 Searching in BS Finding the location of some specific element in
T a binary search tree.

2 Insertion in BST Adding a new element to the binary search tree

at the appropriate location so that the property
of BST do not violate.

3 Deletion in BST Deleting some specific node from a binary

search tree. However, there can be various
cases in deletion depending upon the number
of children, the node have.
Tree Traversal
Here, tree traversal means traversing or visiting each
node of a tree. Linear data structures like Stack, Queue,
linked list have only one way for traversing, whereas the
tree has various ways to traverse or visit each node. The
following are the three different ways of traversal:

•Inorder traversal
•Preorder traversal
•Postorder traversal
Inorder Traversal
An inorder traversal is a traversal technique that
follows the policy, i.e., Left Root Right. Here, Left
Root Right means that the left subtree of the root
node is traversed first, then the root node, and then
the right subtree of the root node is traversed.
Here, inorder name itself suggests that the root
node comes in between the left and the right
subtrees.
Preorder Traversal
A preorder traversal is a traversal technique
that follows the policy, i.e., Root Left Right.
Here, Root Left Right means root node of the
tree is traversed first, then the left subtree and
finally the right subtree is traversed. Here, the
Preorder name itself suggests that the root
node would be traversed first.
Postorder Traversal
A Postorder traversal is a traversal technique
that follows the policy, i.e., Left Right Root.
Here, Left Right Root means the left subtree of
the root node is traversed first, then the right
subtree, and finally, the root node is traversed.
Here, the Postorder name itself suggests that
the root node of the tree would be traversed
at the last.