Tree

A tree is a non-linear data 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.

Basic Terminologies in Tree Data Structure

1. Root: A node of the tree which does not have a parent or the first node of the tree is called
the root of the tree.

2. Leaf node: The last node of the tree which does not have any descendents or the node with
zero out-degree is called leaf node or terminal node.

3. Degree of a node: The number of nodes connected to any node is called the degree of that
node.

4. In-degree of a node: The number of edges that ends at a particular node is called the in-
degree of the node.

5. Our-degree of a node: The number of edges that yields from a particular node is called the
out-degree of that node.

6. Path: A sequence of edges between any two nodes is called the path .

8. Siblings: The children of the same parent node are called siblings.

9. Degree of a tree: The maximum degree of any node is called the degree of a tree.

Tree Applications
1. Hierarchical Organization: Trees are great for organizing data in a hierarchy, like
folders in a computer or categories in a menu.
2. Sorted Storage: Binary search trees help store data in a way that makes searching
fast. They're like a phonebook where you can quickly find a name because it's
organized alphabetically.
3. Keeping Balance: Balanced trees ensure that operations like searching and adding
data stay efficient even as the tree grows. It's like balancing weight evenly on both
sides of a scale.
4. Doing Math: Expression trees help us understand and solve math problems, like
figuring out how to solve a complicated equation step by step.
5. File Systems: Many operating systems use a tree structure to organize files and
directories. Each directory can contain files and other directories, forming a
hierarchical structure.
 6. Organization Charts: Trees are used to represent the hierarchical structure of
organizations, including reporting relationships between employees, departments, and
divisions.

Binary Tree Data Structure

A Binary Tree Data Structure is a hierarchical data structure in which each node has at
most two children, referred to as the left child and the right child. It is commonly used in
computer science for efficient storage and retrieval of data, with various operations such as
insertion, deletion, and traversal.

Basic Operations on Binary Tree:

● Inserting an element.
● Removing an element.
● Searching for an element.
● Deletion for an element.
● Traversing an element. There are four (mainly three) types of traversals in a binary tree
which will be discussed ahead.

Binary Tree Traversals:

Traversing is a process in which each node is visited exactly once. We can perform any
operation on the node traversed; the operation depends on the application.

Tree Traversal algorithms can be classified broadly into two categories:

● Depth-First Search (DFS) Algorithms
● Breadth-First Search (BFS) Algorithms

Tree Traversal using Depth-First Search (DFS) algorithm can be further classified into
three categories:

1. In-order traversal

2. Pre-order traversal.

3. Post-order traversal.

Pre-Order Traversal
In pre-order traversal, the node is traversed first followed by the left subtree in pre-order and
the right subtree. We can write the pre-order traversal as NLR. This is again a recursive
method

In pre-order traversal, the sequence of the steps is as follows

1. Visit the node (N).

2. Visit the left subtree.

3. Visit the right subtree.

Pre-order Traversal of the above tree: 1-2-4-5-3-6-7

Algorithm Pre-order(ptr)

1. If ptr!=NULL

a. Print ptr->info

b. preorder (ptr>left)

c. preorder (ptr->right)

2. Exit

In-Order Traversal

In in-order traversal, the left subtreeis traversed in the inorderfirst followed by the root and
then right subtree. We can write the in-order traversal asLNR. This is again a recursive
method

In in-order traversal, the sequence of the steps is as follows

1. Visit the left subtree.

2. Visit the node (N).

3. Visit the right subtree.

In-order Traversal of the above tree: 4-2-5-1-6-3-7

Algorithm In-order(ptr)

1. If ptr!=NULL

a. in-order (ptr>left)

b. Print ptr->info

c.in-order (ptr->right)

2. Exit

Post-Order Traversal

In post-order traversal, the left subtreeis traversed in post-order first followed by the right
subtree in the post order and then the root. We can write the in-order traversal as LRN. This
is again a recursive method

In post-order traversal, the sequence of the steps is as follows

1. Visit the left subtree.

2. Visit the right subtree.

3. Visit the node (N).

Post-order Traversal of the above tree: 4-5-2-6-7-3-1

Algorithm Post-order(ptr)

1. If ptr!=NULL

a. Post-order (ptr>left)

b. Post-order (ptr->right)

c. Print ptr->info

2. Exit

Tree Traversal using Breadth-First Search (BFS) algorithm can be further classified
into one category:

● Level Order Traversal: Visit nodes level-by-level and left-to-right fashion at the same
level. Here, the traversal is level-wise. It means that the most left child has traversed first
and then the other children of the same level from left to right have traversed.
Let us traverse the following tree with all four traversal methods:

Level-order Traversal of the above tree: 1-2-3-4-5-6-7

Types of Binary Tree

Following are the types of Binary Tree based on the number of children:
1. Full Binary Tree
2. Degenerate Binary Tree
3. Skewed Binary Trees
Full Binary Tree
A Binary Tree is a full binary tree if every node has 0 or 2 children.
Degenerate (or pathological) tree
A degenerate or pathological tree is a tree having a single child either left or
right.

Skewed Binary Tree

Thus, there are two types of skewed binary tree: left-skewed binary tree and
right-skewed binary tree.

Types of Binary Tree On the basis of the completion

of levels:
1. Complete Binary Tree
2. Perfect Binary Tree

1. Complete Binary Tree

A Binary Tree is a Complete Binary Tree if all the levels are completely filled
except possibly the last level and the last level has all keys as left as possible.
In the last level, nodes are added from left to right (no gaps in between).
Perfect Binary Tree
A Binary tree is a Perfect Binary Tree in which all the internal nodes have two
children and all leaf nodes are at the same level.

Binary Tree Representations

A binary tree data structure is represented using two methods. Those methods are as
follows...

1. Array Representation
2. Linked List Representation

Consider the following binary tree

 Array Representation of Binary Tree
In array representation of a binary tree, we use one one-dimensional array (1--D Array) to
represent a binarytree.
Consider the above example of a binary tree and it is represented as follows...

To represent a binary tree of depth 'n' using array representation,

on, we need one dimensional
array with a maximum size of 2n + 11.

Linked List Representation of Binary Tree

We use a double linked list to represent a binary tree. In a double linked list, every node
consists of three fields. First field for storing left child address, second for storing actual data
and third for storing right child address.

In this linked list representation, a node has the following structure...

classNode {
public:
intdata;
Node* left;
Node* right;
};
The above example of the binary tree represented using Linked list representation is shown as
follows...

Binary Search Tree

A Binary Search Tree 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.
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

o First, we have to insert 45 into the tree as the root of the tree.
o Then, read the next element; if it is smaller than the root node, insert it as the root of
the left subtree, and move to the next element.
o Otherwise, if the element is larger than the root node, then insert it as the root of the
right subtree.

Now, let's see the process of creating the Binary search tree using the given data element. The
process of creating the BST is shown below -

Step 1 - Insert 45.

Step 2 - Insert 15.

As 15 is smaller than 45, so insert it as the root node of the left subtree.

Step 3 - Insert 79.

As 79 is greater than 45, so insert it as the root node of the right subtree.
Step 4 - Insert 90.
90 is greater than 45 and 79, so it will be inserted as the right subtree of 79.

Step 5 - Insert 10.

10 is smaller than 45 and 15, so it will be inserted as a left subtree of 15.
Step 6 - Insert 55.
55 is larger than 45 and smaller than 79, so it will be inserted as the left subtree of 79.

Step 7 - Insert 12.

12 is smaller than 45 and 15 but greater than 10, so it will be inserted as the right subtree of
10.
Step 8 - Insert 20.
20 is smaller than 45 but greater than 15, so it will be inserted as the right subtree of 15.

Step 9 - Insert 50.

50 is greater than 45 but smaller than 79 and 55. So, it will be inserted as a left subtree of 55.
Now, the creation of binary search tree is completed.

How to Insert a value in a Binary Search Tree:

Given a BST,, the task is to insert a new node in this BST.

Example:
A new key is always inserted at the leaf by maintaining the property of the binary search
tree. We start searching for a key from the root until we hit a leaf node. Once a leaf node
is found, the new node is added as a child of the leaf node. The below steps are followed
while we try to insert a node into a binary search tree:
● Check the value to be inserted (say X) with the value of the current node (say val) we
are in:
● If X is less than val move to the left subtree.
● Otherwise, move to the right subtree.
● Once the leaf node is reached, insert X to its right or left based on the relation
between X and the leaf node’s value.

Illustration:
Insertion in BST

Insertion in BST
Insertion in BST

Insertion in BST
 Insertion in BST

Algorithm
FUNCTION insert(root, value):

IF root == NULL THEN

RETURN CREATE_NODE(value)

ENDIF

IF value <= root.data THEN

root.left = insert(root.left, value)

ELSE

root.right = insert(root.right, value)

ENDIF

RETURN root

END FUNCTION
Deletion in Binary Search Tree (BST)
Case 1. Delete a Leaf Node in BST

Case 2. Delete a Node with Single Child in BST

Deleting a single child node is also simple in BST. Copy the child to the
node and delete the node
node.

Deletion in BST
Case 3. Delete a Node with Both Children in BST

Deleting a node with both children is not so simple. Here we have to delete
the node is such a way, that the resulting tree follows the properties of a
BST.
Find Max in left, copy the value in targeted node and delete duplicate from
left subtree
Or
Find Min in right, copy the value in targeted node and delete duplicate
from right subtree

The trick is to find the inorder successor of the node. Copy contents of the inorder
successor to the node, and delete the inorder successor.

Note: Inorder predecessor can also be used.

Deletion in Binary Tree

Algorithm
FUNCTION minValueNode(node):

SET current = node

WHILE current is NOT NULL AND current->left is NOT NULL:

 SET current = current->left

END WHILE

RETURN current

FUNCTION deleteNode(root, key):

IF root == NULL:

RETURN root

IF key < root->val:

root->left = deleteNode(root->left, key)

ELSE IF key > root->val:

root->right = deleteNode(root->right, key)

ELSE:

IF root->left == NULL:

SET temp = root->right

DELETE root

RETURN temp

ELSE IF root->right == NULL:

SET temp = root->left

DELETE root

RETURN temp

SET temp = minValueNode(root->right)

root->val = temp->val

root->right = deleteNode(root->right, temp->val)

END IF

RETURN root
 1. Time Complexity
Where 'n' is the number of nodes in the given tree.

Operations Best case time Average case time Worst case time
complexity complexity complexity

Insertion O(log n) O(log n) O(n)

Deletion O(log n) O(log n) O(n)

Search O(log n) O(log n) O(n)

.2. Space Complexity

Operations Space complexity

Insertion O(n)

Deletion O(n)

Search O(n)

Expression Tree

An expression tree is a binary tree where each internal node represents an

operator, and each leaf node represents an operand.

Construct the expression tree for the expression

A-B/C^D+E*F

Solution
In the context provided, the expression tree is constructed using a stack by
looping through the input expression. If a character is an operand, it is pushed
onto the stack. If it is an operator, two values are popped from the stack to create
child nodes, and then the current node is pushed back onto the stack. This
process continues until the entire expression is processed, resulting in the root of
the expression tree.

To evaluate an expression represented by an expression tree, a recursive

approach can be used. Starting from the root of the tree, if a node represents an
operand, its value is returned. If it represents an operator, the left and right
subtrees are recursively evaluated, and then the operator is applied to these
values to calculate the result.