Unit 5: Trees

Syllabus Contents : Tree Terminologies, Traversal Methods, Types of

Trees: General tree, binary tree, binary search tree, Binary tree traversal:
i) In order traversal, ii)preorder traversal, iii)Post order traversal,
Expression tree, AVL search tree, B tree, B+ tree, Heaps- Operations and
their applications, Heap sort

Tree Terminologies:
• 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.

Why Tree is considered a non-linear data structure?

• The data in a tree are not stored in a sequential manner i.e., they are not
stored linearly. Instead, they are arranged on multiple levels or we can
say it is a hierarchical structure. For this reason, the tree is considered to
be a non-linear data structure.
Basic Terminologies In Tree Data Structure:
• Parent Node: The node which is an immediate 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.
• Neighbour 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.
Representation of Tree Data Structure:
A tree consists of a root node, and zero or more subtrees T1, T2, … , Tk such
that there is an edge from the root node of the tree to the root node of each
subtree. Subtree of a node X consists of all the nodes which have node X as the
ancestor node.

Representation of a Node in Tree Data Structure:

A tree can be represented using a collection of nodes. Each of the nodes can be
represented with the help of class or structs. Below is the representation of Node
in different languages:

struct Node {
int data;
struct Node* first_child;
struct Node* second_child;
struct Node* third_child;
.
.
.
struct Node* nth_child;
};
Types of Trees: General tree, binary tree, binary search tree

General tree binary tree

• In the data structure, General tree is a tree in which each node can have
either zero or many child nodes.
• It can not be empty.
• In general tree, there is no limitation on the degree of a node. The
topmost node of a general tree is called the root node.
• There are many subtrees in a general tree. The subtree of a general tree is
unordered because the nodes of the general tree can not be ordered
according to specific criteria.
• In a general tree, each node has in-degree(number of parent nodes) one
and maximum out-degree(number of child nodes) n.

Binary tree

• A binary tree is the specialized version of the General tree.

• A binary tree is a tree in which each node can have at most two nodes.
• In a binary tree, there is a limitation on the degree of a node because the
nodes in a binary tree can’t have more than two child node (or degree
two).
• The topmost node of a binary tree is called root node and there are mainly
two subtrees one is left-subtree and another is right-subtree.
• Unlike the general tree, the binary tree can be empty.
• Unlike the general tree, the subtree of a binary tree is ordered because the
nodes of a binary tree can be ordered according to specific criteria.
Difference between General tree and Binary tree
General tree Binary tree

General tree is a tree in which

Whereas in binary tree, each node can have at
each node can have many
most two nodes.
children or nodes.

The subtree of a general tree do While the subtree of binary tree hold the ordered
not hold the ordered property. property.

In data structure, a general tree

While it can be empty.
can not be empty.

In general tree, a node can have

While in binary tree, a node can have at
at most n(number of child
most 2(number of child nodes) nodes.
nodes) nodes.

In general tree, there is no While in binary tree, there is limitation on the

limitation on the degree of a degree of a node because the nodes in a binary
node. tree can’t have more than two child node.

In general tree, there is either While in binary tree, there are mainly two
zero subtree or many subtree. subtree: Left-subtree and Right-subtree.
Binary search tree

• A Binary Search Tree (or BST) is a data structure used in computer

science for organizing and storing data in a sorted manner.
• Each node in a Binary Search Tree has at most two children, a left child
and a right child, with the left child containing values less than the parent
node and the right child containing values greater than the parent node.
• This hierarchical structure allows for efficient searching, insertion,
and deletion operations on the data stored in the tree.

Properties of Binary Search Tree:

• The left subtree of a node contains only nodes with keys lesser than the
node’s key.
• The right subtree of a node contains only nodes with keys greater than the
node’s key.
• The left and right subtree each must also be a binary search tree.
• There must be no duplicate nodes(BST may have duplicate values with
different handling approaches).
 • A BST supports operations like search, insert, delete, maximum,
minimum, floor, ceil, greater, smaller, etc in O(h) time where h is height
of the BST.
• To keep height less, self balancing BSTs (like AVL and Red Black Trees)
are used in practice. These Self-Balancing BSTs maintain the height as
O(Log n). Therefore all of the above mentioned operations become
O(Log n).

Applications of BST
Together with these, BST also allows sorted order traversal of data in O(n) time.
1. A Self-Balancing Binary Search Tree is used to maintain sorted stream of
data. For example, suppose we are getting online orders placed and we
want to maintain the live data (in RAM) in sorted order of prices. For
example, we wish to know number of items purchased at cost below a
given cost at any moment. Or we wish to know number of items
purchased at higher cost than given cost.
2. A Self-Balancing Binary Search Tree is used to implement doubly ended
priority queue. With a Binary Heap, we can either implement a priority
queue with support of extractMin() or with extractMax(). If we wish to
support both the operations, we use a Self-Balancing Binary Search Tree
to do both in O(Log n)
3. There are many more algorithm problems where a Self-Balancing BST is
the best suited data structure, like count smaller elements on
right, Smallest Greater Element on Right Side, etc.
4. A BST can be used to sort a large dataset. By inserting the elements of
the dataset into a BST and then performing an in-order traversal, the
elements will be returned in sorted order. When compared to normal
sorting algorithms, the advantage here is, we can later insert / delete items
in O(Log n) time.
5. Variations of BST like B Tree and B+ Tree are used in Database
indexing.
6. TreeMap and TreeSet in Java, and set and map in C++ are internally
implemented using self-balancing BSTs, more formally a Red-Black
Tree.
Binary tree traversal:
i) In order traversal
ii)preorder traversal
iii)Post order traversal

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

A Tree Data Structure can be traversed in following ways:

• Depth First Search or DFS
o Inorder Traversal
o Preorder Traversal
o Postorder Traversal
• 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)
• Visit the root.
• Traverse the right subtree, i.e., call Inorder(right->subtree)
Preorder Traversal:

Preorder traversal visits the node in the order: Root -> Left -> Right

Algorithm for Preorder Traversal:

Preorder(tree)
• Visit the root.
• Traverse the left subtree, i.e., call Preorder(left->subtree)
• Traverse the right subtree, i.e., call Preorder(right->subtree)
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)
• Visit the root

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)
• Create an empty queue Q
• Enqueue the root node of the tree to Q
• Loop while Q is not empty
o Dequeue a node from Q and visit it
o Enqueue the left child of the dequeued node if it exists
o Enqueue the right child of the dequeued node if it exists
Expression tree
• The expression tree is a binary tree in which each internal node
corresponds to the operator and each leaf node corresponds to the
operand
• so for example expression tree for 3 + ((5+9)*2) would be:

• Inorder traversal of expression tree produces infix version of given

postfix expression (same with postorder traversal it gives postfix
expression)
Evaluating the expression represented by an expression tree:
Let t be the expression tree
If t is not null then
If t.value is operand then
Return t.value
A = solve(t.left)
B = solve(t.right)

// calculate applies operator 't.value'

// on A and B, and returns value
Return calculate(A, B, t.value)

Construction of Expression Tree:

Now For constructing an expression tree we use a stack. We loop through input
expression and do the following for every character.
1. If a character is an operand push that into the stack
2. If a character is an operator pop two values from the stack make them its
child and push the current node again.
In the end, the only element of the stack will be the root of an expression tree.
Examples:
Input: A B C*+ D/
Output: A + B * C / D
The first three symbols are operands, so create tree nodes and push pointers to
them onto a stack as shown below.

In the Next step, an operator ‘*’ will going read, so two pointers to trees are
popped, a new tree is formed and a pointer to it is pushed onto the stack
In the Next step, an operator ‘+’ will read, so two pointers to trees are popped,
a new tree is formed and a pointer to it is pushed onto the stack.

Similarly, as above cases first we push ‘D’ into the stack and then in the last
step first, will read ‘/’ and then as previous step topmost element will pop out
and then will be right subtree of root ‘/’ and other nodes will be right
subtree.