Trees

What are Trees?

A tree is a collection of entities called nodes.
Nodes are connected by edges.
Each node contains a value or data, and it may or may not have a child node .

The first node of the tree is called the root. If this root node is connected by another node,
the root is then a parent node and the connected node is a child.

All Tree nodes are connected by links called edges. It’s an important part of trees, because it’s
manages the relationship between nodes.
 Leaves are the last nodes on a tree. They are nodes without children. Like real trees, we have
the root, branches, and finally the leaves.

Other important concepts to understand are height and depth.

The height of a tree is the length of the longest path to a leaf.
The depth of a node is the length of the path to its root.
Terminology summary
 Root is the topmost node of the tree
 Edge is the link between two nodes
 Child is a node that has a parent node
 Parent is a node that has an edge to a child node
 Leaf is a node that does not have a child node in the tree
 Height is the length of the longest path to a leaf
 Depth is the length of the path to its root

Properties of Tree: Every tree has a specific root node. Each tree node can be crossed by a
root node. It is called root, as the tree was the only root. Every child has only one parent, but
the parent can have many children.

Types of Trees in Data Structure

Below are the types of trees in a data structure:

1. General Tree
If no constraint is placed on the hierarchy of the tree, a tree is called a general tree. Every
node may have infinite numbers of children in General Tree. The tree is the super-set of all
other trees.

2. Binary Tree
The binary tree is the kind of tree in which most two children can be found for each parent.
The kids are known as the left kid and right kid. This is more popular than most other trees.
When certain constraints and characteristics are applied in a Binary tree, a number of others
such as AVL tree, BST (Binary Search Tree), RBT tree, etc. are also used. When we move
forward, we will explain all these styles in detail.

3. Binary Search Tree

Binary Search Tree (BST) is a binary tree extension with several optional restrictions. The
left child value of a node should in BST be less than or equal to the parent value and the right
child value should always be greater than or equal to the parent’s value. This Binary Search
Tree property makes it ideal for search operations since we can accurately determine at each
node whether the value is in the left or right sub-tree. This is why the Search Tree is named.

4. AVL Tree
AVL tree is a binary search tree self-balancing. On behalf of the inventors Adelson-Velshi
and Landis, the name AVL is given. This was the first tree that balanced dynamically. A
balancing factor is allocated for each node in the AVL tree, based on whether the tree is
balanced or not. The height of the node kids is at most 1. AVL vine. In the AVL tree, the
correct balance factor is 1, 0 and -1. If the tree has a new node, then it will be rotated to
ensure that the tree is balanced. It will then be rotated. Common operations such as viewing,
insertion, and removal take O(log n) time in the AVL tree. It is mostly applied when working
with Lookups operations.
5. Red-Black Tree
Another kind of auto-balancing tree is red-black. The red-black name is given because the
Red-black tree has either red or Black painted on each node according to the red-black tree’s
properties. It maintains the balance of the forest. Even though this tree is not a fully balanced
tree, the searching operation only takes O (log n) time. When the new nodes are added in
Red-Black Tree then nodes will be rotated again to maintain the Red-Black Tree’s properties.

6. N-ary Tree
The maximum number of children in this type of tree that can have a node is N. A binary tree
is a twoyear tree, as at most 2 children in every binary tree node. A complete N-ary tree is a
tree where kids of a node either are 0 or N.

Advantages of Tree
Now we will understand the Advantages of Tree:

• Tree reflects in the data structural connections.

 • The tree is used for hierarchy.

• It offers an efficient search and insertion procedure.

• The trees are flexible. This allows subtrees to be relocated with minimal effort.

Tree represents the nodes connected by edges. We will discuss binary tree or binary search
tree specifically.
Binary Tree is a special datastructure used for data storage purposes. A binary tree has a
special condition that each node can have a maximum of two children. A binary tree has the
benefits of both an ordered array and a linked list as search is as quick as in a sorted array
and insertion or deletion operation are as fast as in linked list.

Important Terms

Following are the important terms with respect to tree.

• Path − Path refers to the sequence of nodes along the edges of a tree.
• Root − The node at the top of the tree is called root. There is only one root per tree
and one path from the root node to any node.
• Parent − Any node except the root node has one edge upward to a node called
parent.
• Child − The node below a given node connected by its edge downward is called its
child node.
• Leaf − The node which does not have any child node is called the leaf node.
• Subtree − Subtree represents the descendants of a node.
• Visiting − Visiting refers to checking the value of a node when control is on the
node.
• Traversing − Traversing means passing through nodes in a specific order.
 • Levels − Level of a node represents the generation of a node. If the root node is at
level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.
• keys − Key represents a value of a node based on which a search operation is to be
carried out for a node.

Binary Search Tree Representation

Binary Search tree exhibits a special behavior. A node's left child must have a value less than
its parent's value and the node's right child must have a value greater than its parent value.

We're going to implement tree using node object and connecting them through references.

Tree Node

The code to write a tree node would be similar to what is given below. It has a data part and
references to its left and right child nodes.
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
In a tree, all nodes share common construct.

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.
We shall learn creating (inserting into) a tree structure and searching a data item in a tree in
this chapter. We shall learn about tree traversing methods in the coming chapter.

Insert Operation

The very first insertion creates the tree. Afterwards, whenever an element is to be inserted,
first locate its proper location. Start searching from the root node, then if the data is less than
the key value, search for the empty location in the left subtree and insert the data. Otherwise,
search for the empty location in the right subtree and insert the data.

Algorithm

If root is NULL
then create root node
return

If root exists then

compare the data with node.data

while until insertion position is located

If data is greater than node.data

goto right subtree
else
goto left subtree

endwhile

insert data

end If
Implementation

The implementation of insert function should look like this −

void insert(int data) {
struct node *tempNode = (struct node*) malloc(sizeof(struct
node)); struct node *current;
struct node *parent;

tempNode->data = data; tempNode-

>leftChild = NULL;
tempNode->rightChild = NULL;

//if tree is empty, create root node

if(root == NULL) {
root = tempNode;
} else
{ current =
root;
parent = NULL;

while(1) {
parent = current;

//go to left of the tree

if(data < parent->data) {
current = current->leftChild;

//insert to the left

if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}

//go to right of the tree

else {
current = current->rightChild;

//insert to the right

if(current == NULL) {
parent->rightChild = tempNode;
return;
}
}
}
}
}
Search Operation

Whenever an element is to be searched, start searching from the root node, then if the data is
less than the key value, search for the element in the left subtree. Otherwise, search for the
element in the right subtree. Follow the same algorithm for each node.
Algorithm
If root.data is equal to
search.data return root
else
while data not found

If data is greater than

node.data
goto right subtree
else
goto left subtree

If data found
return node
endwhile

return data not found

end
if
The implementation of this algorithm should look like this.
struct node* search(int data)
{ struct node *current = root;
printf("Visiting elements: ");

while(current->data != data)
{ if(current != NULL)
printf("%d ",current->data);

//go to left tree

if(current->data > data) {

current = current->leftChild;
}
//else go to right tree
else {
current = current->rightChild;
}

//not found
if(current == NULL) {
return NULL;
}

return current;
}
}
 Traversal is a process to visit all the nodes of a tree and may print their values too. Because,
all nodes are connected via edges (links) we always start from the root (head) node. That is,
we cannot randomly access a node in a tree. There are three ways which we use to traverse a
tree –

• Pre-order Traversal
• In-order Traversal
• Post-order Traversal
Generally, we traverse a tree to search or locate a given item or key in the tree or to print all
the values it contains.

Depth-First Search (DFS)

DFS explores a path all the way to a leaf before backtracking and exploring another path. Let’s
take a look at an example with this type of traversal.

The result for this algorithm will be 1–2–3–4–5–6–7.

Why?

Let’s break it down.

1. Start at the root (1). Print it.

2. Go to the left child (2). Print it.
3. Then go to the left child (3). Print it. (This node doesn’t have any children)
4. Backtrack and go the right child (4). Print it. (This node doesn’t have any children)
5. Backtrack to the root node and go to the right child (5). Print it.
6. Go to the left child (6). Print it. (This node doesn’t have any children)
7. Backtrack and go to the right child (7). Print it. (This node doesn’t have any children)
8. Done.

When we go deep to the leaf and backtrack, this is called DFS algorithm.
Now that we are familiar with this traversal algorithm, we will discuss types of DFS: pre-
order, in-order, and post-order.
Pre-order Traversal

1. Print the value of the node.

2. Go to the left child and print it. This is if, and only if, it has a left child.
3. Go to the right child and print it. This is if, and only if, it has a right child.
def pre_order(self):
print(self.value)

if self.left_child:
self.left_child.pre_order()

if self.right_child:
self.right_child.pre_order()

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

Algorithm

Until all nodes are traversed −

Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.
 In-order Traversal

The result of the in-order algorithm for this tree example is 3–2–4–1–6–5–7.
The left first, the middle second, and the right last.

Now let’s code it.

def in_order(self):
if self.left_child:
self.left_child.in_order()

print(self.value)

if self.right_child:
self.right_child.in_order()
1. Go to the left child and print it. This is if, and only if, it has a left child.
2. Print the node’s value
3. Go to the right child and print it. This is if, and only if, it has a right child.

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 in-order, the output will produce sorted key values in an
ascending order.
We start from A, and following in-order traversal, we move to its left subtree B. B is also
traversed inorder. 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

Algorithm

Until all nodes are traversed −

Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

Post-order Traversal
 Post-order

The result of the post order algorithm for this tree example is 3–
4–2–6–7–5–1.
The left first, the right second, and the middle last.

Let’s code this.

def post_order(self):
if self.left_child:
self.left_child.post_order()

if self.right_child:
self.right_child.post_order()

print(self.value)
1. Go to the left child and print it. This is if, and only if, it
has a left child.
2. Go to the right child and print it. This is if, and only if, it
has a right child.
3. Print the node’s value
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.

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

Algorithm

Until all nodes are traversed −

Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned
properties − The left sub-tree of a node has a key less than or equal to its parent node's key.

The right sub-tree of a node has a key greater than to its parent node's key.

Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree
and can be defined as −

left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)

Representation

BST is a collection of nodes arranged in a way where they maintain BST properties. Each
node has a key and an associated value. While searching, the desired key is compared to the
keys in BST and if found, the associated value is retrieved.
Following is a pictorial representation of BST −

Binary Search Tree

We observe that the root node key (27) has all less-valued keys on the left sub-tree and the
higher valued keys on the right sub-tree.

Basic Operations

Following are the basic operations of a tree −

Search − Searches an element in a tree.

Insert − Inserts an element in a tree.

Pre-order Traversal − Traverses a tree in a pre-order manner.

In-order Traversal − Traverses a tree in an in-order manner.

Post-order Traversal − Traverses a tree in a post-order manner.

Node

Define a node having some data, references to its left and right child nodes.

struct node {

int data; struct

node *leftChild;
struct node
*rightChild;
};

Search Operation
Whenever an element is to be searched, start searching from the root node. Then if the data is
less than the key value, search for the element in the left subtree. Otherwise, search for the
element in the right subtree. Follow the same algorithm for each node.

Algorithm struct node*

search(int data){ struct
node *current = root;
printf("Visiting elements:
");

while(current->data != data){

if(current != NULL) {
printf("%d ",current->data);

//go to left tree

if(current->data > data){
current = current->leftChild;
} //else go to right tree
else { current
= current->rightChild;
}

//not found
if(current == NULL){
return NULL;
}

return current;

Insert Operation

Whenever an element is to be inserted, first locate its proper location. Start searching from the
root node, then if the data is less than the key value, search for the empty location in the left
subtree and insert the data. Otherwise, search for the empty location in the right subtree and
insert the data.
Algorithm void insert(int data) { struct node *tempNode =
(struct node*) malloc(sizeof(struct node)); struct node
*current; struct node *parent;

tempNode->data = data; tempNode-

>leftChild = NULL; tempNode-
>rightChild = NULL;

//if tree is empty

if(root == NULL) {
root = tempNode;
} else
{ current =
root; parent =
NULL;
while(1) {
parent = current;

//go to left of the tree

if(data < parent->data) {
current = current->leftChild;
//insert to the left

if(current == NULL)
{ parent->leftChild =
tempNode;
return;

} //go to right of the tree

else { current = current-
>rightChild;

//insert to the right

if(current == NULL) {
parent->rightChild =
tempNode;

return;

}
 }

What if the input to binary search tree comes in a sorted (ascending or descending) manner?
It will then look like this −

It is observed that BST's worst-case performance is closest to linear search algorithms, that
is Ο(n). In real-time data, we cannot predict data pattern and their frequencies. So, a need
arises to balance out the existing BST.
Named after their inventor Adelson, Velski & Landis, AVL trees are height balancing
binary search tree. AVL tree checks the height of the left and the right subtrees and assures
that the difference is not more than 1. This difference is called the Balance Factor.
Here we see that the first tree is balanced and the next two trees are not balanced −

In the second tree, the left subtree of C has height 2 and the right subtree has height 0, so the
difference is 2. In the third tree, the right subtree of A has height 2 and the left is missing, so
it is 0, and the difference is 2 again. AVL tree permits difference (balance factor) to be only
1.
BalanceFactor = height(left-sutree) − height(right-sutree)
If the difference in the height of left and right sub-trees is more than 1, the tree is balanced
using some rotation techniques.

AVL Rotations
To balance itself, an AVL tree may perform the following four kinds of rotations −

• Left rotation
• Right rotation
• Left-Right rotation
• Right-Left rotation
The first two rotations are single rotations and the next two rotations are double rotations. To
have an unbalanced tree, we at least need a tree of height 2. With this simple tree, let's
understand them one by one.

Left Rotation

If a tree becomes unbalanced, when a node is inserted into the right subtree of the right
subtree, then we perform a single left rotation −

In our example, node A has become unbalanced as a node is inserted in the right subtree of
A's right subtree. We perform the left rotation by making A the left-subtree of B.

Right Rotation

AVL tree may become unbalanced, if a node is inserted in the left subtree of the left subtree.
The tree then needs a right rotation.

As depicted, the unbalanced node becomes the right child of its left child by performing a
right rotation.

Left-Right Rotation

Double rotations are slightly complex version of already explained versions of rotations. To
understand them better, we should take note of each action performed while rotation. Let's
first check how to perform Left-Right rotation. A left-right rotation is a combination of left
rotation followed by right rotation.
State Action

A node has been inserted into the right subtree of the left subtree. This
makes C an unbalanced node. These scenarios cause AVL tree to
perform left-right rotation.

We first perform the left rotation on the left subtree of C. This makes
A, the left subtree of B.

Node C is still unbalanced, however now, it is because of the left-

subtree of the left-subtree.

We shall now right-rotate the tree, making B the new root node of this
subtree. C now becomes the right subtree of its own left subtree.
 The tree is now balanced.

Right-Left Rotation

The second type of double rotation is Right-Left Rotation. It is a combination of right

rotation followed by left rotation.
State Action

A node has been inserted into the left subtree of the right subtree. This
makes A, an unbalanced node with balance factor
2.

First, we perform the right rotation along C node, making C the right
subtree of its own left subtree B. Now, B becomes the right subtree of
A.

Node A is still unbalanced because of the right subtree of its right

subtree and requires a left rotation.
 A left rotation is performed by making B the new root node of the
subtree. A becomes the left subtree of its right subtree B.

The tree is now balanced.

Difference between Binary Search Tree and Linked Lists

Linked List :

Node(1) -> Node(2) -> Node(3) -> Node(4) -> Node(5) -> Node(6) -> Node(7)

 In linked list, the items are linked together through a single next pointer.
 Next Node’s Key Can be larger or samller then previous Node.
 Not Sorted

 Time Complexity of Search :O(n) Insert : O(1) Delete : O(1) {if you have use optimized
method }

Binary Search Tree:

[4]
/ \
[2] [6]
/ \ / \
[1] [3] [5] [7]

 In a binary tree, each node can have 0, 1 or 2 sub nodes.

 The key of the left node is lesser than the key of the node and the key of the right node is
more than the node
 Sorted
 Time Complexity of Search : O(log(n)) Insert : O(log(n)) Delete : O(log(n))
Expression Tree
Expression tree is a binary tree in which each internal node corresponds to operator and each leaf
node corresponds to 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
preorder traversal it gives prefix expression)
Evaluating the expression represented by 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 expression tree we use a stack. We loop through input expression and do
following for every character.
1) If character is operand push that into stack
2) If character is operator pop two values from stack make them its child and push current node
again.
At the end only element of stack will be root of expression tree.

C++

// C++ program for expression tree

#includestd>
using namespace std;

// An expression tree node

struct et

char value;

et* left, *right;

};

// A utility function to check if 'c'

// is an operator

bool isOperator(char c)

if (c == '+' || c == '-' ||

c == '*' || c == '/' ||

c == '^')

return true;

return false;

// Utility function to do inorder traversal

void inorder(et *t)

if(t)

inorder(t->left);

printf("%c ", t->value);

inorder(t->right);
 }

// A utility function to create a new node

et* newNode(int v)

et *temp = new et;

temp->left = temp->right = NULL;

temp->value = v;

return temp;

};

// Returns root of constructed tree for given

// postfix expression

et* constructTree(char postfix[])

stack<et *> st;

et *t, *t1, *t2;

// Traverse through every character of

// input expression

for (int i=0; i<strlen(postfix); i++)

// If operand, simply push into stack

if (!isOperator(postfix[i]))

t = newNode(postfix[i]);
 st.push(t);

else // operator

t = newNode(postfix[i]);

// Pop two top nodes

t1 = st.top(); // Store top

st.pop(); // Remove top

t2 = st.top();

st.pop();

// make them children

t->right = t1;

t->left = t2;

// Add this subexpression to stack

st.push(t);

// only element will be root of expression

// tree

t = st.top();

st.pop();

return t;
}

// Driver program to test above

int main()

char postfix[] = "ab+ef*g*-";

et* r = constructTree(postfix);

printf("infix expression is \n");

inorder(r);

return 0;

Tree Sort
Tree sort is a sorting algorithm that is based on Binary Search Tree data structure. It first creates a
binary search tree from the elements of the input list or array and then performs an in-order
traversal on the created binary search tree to get the elements in sorted order.
Algorithm:
Step 1: Take the elements input in an array.
Step 2: Create a Binary search tree by inserting data items from the array into the
binary search tree.
Step 3: Perform in-order traversal on the tree to get the elements in sorted order.

// C++ program to implement Tree Sort

#includeiostream

using namespace std;

struct Node

int key;

struct Node *left, *right;

};

// A utility function to create a new BST Node

struct Node *newNode(int item)

{

struct Node *temp = new Node;

temp->key = item;

temp->left = temp->right = NULL;

return temp;

// Stores inoder traversal of the BST

// in arr[]

void storeSorted(Node *root, int arr[], int &i)

if (root != NULL)

storeSorted(root->left, arr, i);

arr[i++] = root->key;

storeSorted(root->right, arr, i);

/* A utility function to insert a new

Node with given key in BST */

Node* insert(Node* node, int key)

/* If the tree is empty, return a new Node */

if (node == NULL) return newNode(key);

/* Otherwise, recur down the tree */

if (key < node->key)

node->left = insert(node->left, key);

 else if (key > node->key)

node->right = insert(node->right, key);

/* return the (unchanged) Node pointer */

return node;

// This function sorts arr[0..n-1] using Tree Sort

void treeSort(int arr[], int n)

struct Node *root = NULL;

// Construct the BST

root = insert(root, arr[0]);

for (int i=1; i<n; i++)

root = insert(root, arr[i]);

// Store inoder traversal of the BST

// in arr[]

int i = 0;

storeSorted(root, arr, i);

// Driver Program to test above functions

int main()

//create input array

int arr[] = {5, 4, 7, 2, 11};

int n = sizeof(arr)/sizeof(arr[0]);

treeSort(arr, n);

for (int i=0; i<n; i++)

 cout << arr[i] << " ";

return 0;