Trees
Anirudh Agnihotry
INTRODUCTION
Arrays , stacks , linked lists , queues are linear data structures whereas trees
are hierarchical data structures.
Trees are of various types e.g. binary trees ,Avl trees , Binary search trees.
A tree whose elements have at most two children is called a binary tree . As it
can have only two children we call them as left and right child
Structure of Node
A node in a tree consists of following parts
Data
Pointer to right child
Pointer to left child
Parent pointer (optional)
The topmost node is called root of the tree .
The nodes which does not have any child nodes are called as leaves.
Rest of the nodes are called as internal nodes.
Continued ...
5
root
Internal
node
leaf
struct node
{
int data;
struct node *left;
struct node *right;
};
Create an Empty Tree
int main()
{
node* root = NULL;
return 0;
}
Creating a new Node
//create node and allocate memory
node* create_node(int data)
{
node* new_node = (node*) malloc(sizeof(node));
new_node->val = val;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
Building a Tree
int main()
{
node* root=create_node(5);
//creating left child
root->left=create_node(2);
//creating right child
root->right=create_node(7);
return 0;
}
Traversing a Binary Tree
To traverse (or walk) the binary tree is to visit each node in the binary tree
exactly once
There are three kinds of traversals
Preorder :- node,left,right
Inorder :- left,node,right
Postorder:- left,right,root
Traversals are generally recursive
Inorder walk
Inorder walk(root)
1.
2.
3.
Inorder walk(root->left)
Visit node
Inorder walk(root->right)
Time Complexity ?
void Inorderwalk(Node* root)
{
if(root == NULL)//base case
return;
Else{
Inorderwalk(root->left);
printf(%d,root->data);
Inorderwalk(root->right);
}
}
Inorder traversal :- 9,2,7,5,6,1
Preorder traversal ???
Postorder traversal ???
Search for a key
Given a key we have to find if it is present in binary tree.
bool IsPresent(Node* root,int key)
{
if(root == NULL)//base case
return false;
Else if(root->data == key)
return true;
Else{
return IsPresent(root->left,key) ||
IsPresent(root->right,key);
}
}
Time complexity ?
Height of a Tree
Height of a node is the length of the longest path in its subtree to a leaf
Height of a Binary Tree is the height of its root node.
Given a Binary Tree, write a function which calculates its height.
Height of binary tree (Conti)
int height(Node* root)
{
if(root == NULL)//base case
Return -1;
Else{
Return max(height(root->left),height(root->right))+1;
}
}
Time complexity ?
Height of a leaf ?
Maximum height possible with N nodes ?
Questions ?
Binary Search Trees
A Binary search tree is a binary tree with following properties
The left subtree of a nodes contains nodes with keys with value less than its own key
The right subtree of a nodes contains nodes with keys with value higher than its own key
The left subtree and right subtree should be binary search trees
The above ordering among keys make search operation faster but slows
down insertion.
Examples
2
10
11
6
2
15
Search for a key in a Bst
Given a key we have to find node containing the key.
Node* search(Node* root,int key)
{
if(root == NULL)//base case
return NULL;
Else if(root->data == key)
return root;
Else if(root->data > key){
Return search(root->left,key);
}
Else{
Return search(root->right,key);
}
}
Time complexity ?
Space Complexity ?
Complexity
Time : O(h) where h is the height of the tree.
In the worst case, h may be O(n)!
Space : Need O(h) for stack space for the recursive algorithm. It can be done
iteratively in constant space.
Insert In a BST
Algorithm(key)
We need to insert a new value in a tree preserving its bst structure.
starting at the root it probes down the tree till it finds a node whose left or
right pointer is empty and is a logical place for the new value.
Time Complexity is O(h)
Case 1:- The tree is empty
Set the root to a new node containing the item
Case 2:- The tree is not empty
Call a recursive helper method to insert the item
10
Insert 12
12 > 10
13
13>12
12
15
Code for Insertion
Node* insert(Node* root,int key)
{
if(root == NULL) //base case
return create_node(key);
Else if(root->data > key){
root->left = insert(root->left,key);
Return root;
}
Else{
root->right = insert(root->right,key);
Return root;
}
}
10
Int main()
{
node* root = NULL;
root = Insert(root,10);
Insert(root,20);
Insert(root,30);
}
20
30
Deletion in BST
delete(root,key)
1.
2.
If the tree is empty then just return
Search the key in the tree
a.
b.
3.
If not found then return
If found then proceed to step 3
Now the problem can divided into various scenarios
a.
b.
c.
d.
Case 1 :- The node has no children then replace the link in parent node with NULL
Case 2:- the node has both left and right child
i. Find the leftmost element in right subtree and leftmost element in right subtree,swap
with the node.
ii. Now delete the leftmost element
Case 3:- The node has no left child
i. Link the parent of the node to right subtree
Similarly when the node has no right child
Case 1:- delete node with no empty subtrees(leaf)
Delete 12
7
parent
10
12
Removing 12
replace the link in the parent with
null
Case 2:- delete node with one subtree
Delete 10
7
10
Removing 10
replace the link in the parent with its
non-null child
Case 3:- delete node with both subtrees
Delete 4
7
Removing 4
Swap 4 with the leftmost node and
remove not that node.
Final tree
Properties of BST
Inorder traversal of bst traverses the nodes in sorted order
Insertion, deletion and search takes O(h) time.
The minimum possible height for n nodes in bst is O(logn)
The maximum possible height for n nodes in bst is O(n)
Find smallest and largest element in a bst
Solution :- Find the leftmost element of bst for smallest element and rightmost
element for largest element
Node* smallest(Node* root)
{
if(root == NULL) //base case
return NULL;
Else if(root->left == NULL){
return root;
}
Else if{
return smallest(root->left);
}
}
Balanced Binary Trees
The balanced binary trees are those trees in which the height difference of left
child node and right child node is atmost 1.
Height of such trees become atmost O(logn).
So all the insert,search and delete operations can be done in O(logn).
Thanks :)
