Data Structures & Algorithms – Tree

Posted byrscodelifePosted inAlgorithms, Basic, Binary Search Tree, codelife, codeNewbie, Coding, Data Structures, Programming, rscodelifeTags:, , , , , , ,
Data Structures & Algorithms – Tree

Welcome back,

This is our fourth module of Data Structures and Algorithms. In our previous module we discussed Queue ADT, Queue Operations and Applications, Array implementation of Queue, Circular Array implementation of Queue, Linked list implementation of Queue concepts.

In this module, we will discuss the following:

4. Tree ADT:

4.1 Binary Search Tree(BST) implementation

4.2 Finding min and max element in a BST

4.3 Find height of BST

4.4 BST traversal breadth first,depth first

4.5 Level order traversal

4.6 Preorder, Inorder and PostOrder traversal

4.7 Checking whether a Binary tree is BST

4.8 Deleting a node from BST

4. Tree ADT:

Tree :

It is a Non-linear hierarchial (and recursive) data structure. Whereas LINEAR DATA STRUCTURES consists of prev, next elements, they have their data in a sequential manner with a LOGICAL START and END. Linear data structures are Array, L.L, Stack, Queue.

Tree is a recursive data structure. Since Tree is divided into subtrees, they also follow the hierarchical arrangement. Tree is used to store data which are naturally hierarchical, say files and folders in disk drive.

Tree Definition :

Tree is a collection of entity called “NODE”,linked together to simulate a hierarchy. Node contains data of any type .,i.e object. The hierarchical link gives parent/children relationship.

Tree Vocabulary:

  1. Root
  2. Children/Child
  3. Parent
  4. Sibling
  5. Leaf- A node with no child (rest of the nodes are internal nodes)
  6. Ancestor / Descendant

Tree Properties:

  1. Recursive data structure
  2. For a tree with N nodes, there will be (N-1) edges.
  3. Depth / Height

Depth of x = length of path from root to x (Or)

Depth of x = No. of edges in path from root to x

Remember, Depth of root = 0 (food for thought..!!)

Height of x = No. Of edges in LONGEST PATH from x to a leaf

Remember,

Height of leaf node = 0

Height of root node = Height of the tree

Max depth of b/n tree = Height of b/n tree

Applications of Tree :

  1. Storing naturally hierarchical data

eg: file system in disk drive, files/folders in disk

  1. Organizing data for quick search, insertion, deletion

eg: Binary Search Tree. BST is the efficient way to store ordered data, with a time complexity of log2 n.

  1. Network Routing Algorithm.
  2. Special tree called TRIE is used to store dictionary for dynamic spell checking.

Binary Tree :

A tree in which each Node can have atmost 2 children.

Syntax:

struct Node{
		int data;
		Node* left;  //pointer to left child
		Node* right;  //pointer to right child
	};
	Node* root;  //pointer to root node

Diff. ways of representing Binary Tree :

  1. A Node itself is a B/n tree

eg: A single Node alone is a B/n tree

  1. A tree with only left or right chidren is a B/n tree
  2. A tree with both right and left children, but the subtrees have either right or left children. Since a Node cannot have more than 2 children, but less than 2, say 0 or 1 is accepted

Property of Binary Tree :

Max no. Of Nodes in a level = 2i , where i -is level

Max no. Of Nodes in a B/n tree = 2h+1 -1, where h -is height

i.e., 20 +21 +……2h = 2(no. Of levels)-1

Types of Binary Tree :

  1. Strict / Proper Binary tree
  2. Complete Binary tree
  3. Perfect Binary tree
  4. Balanced Binary tree
  5. Binary search tree

1.Strict / Proper Binary Tree :

Each Node can have either 2 or 0 children. (One child is NOT ALLOWED)

2. Complete Binary Tree :

All levels except possibly the last are completely filled and all Nodes are as left as possible. (last but one level should be completely filled)

Height of complete B/n tree ( h) = log2 n, where n – is number of Nodes.

3. Perfect Binary Tree :

All levels must be completely filled.

Max no. Of Nodes in a B/n tree = 2h+1 -1, where h -is height

Height of perfect B/n tree : h= log2 (n+1)-1, where n – is no. Of Nodes.

Note: Perfect B/n tree is also a Complete b/n tree

4. Balanced Binary Tree :

Diff between the height of left and right subtree for every Node is not more than k (mostly 1)

5. Binary Search Tree (BST) :

A Binary tree, in which for each Node, value of all the Nodes in left subtree is lesser (or equal) and value of all the Nodes in right subtree is greater.

Note:

  1. Time complexity is directly proportional to Height of BST, so keep the height less, but denser
  2. Inorder traversal of BST gives sorted list

4.1 Binary Search Tree (BST) implementation

Runnable Code Snippet_4.1 – Binary Search Tree (BST) implementation

/* 4.1 BST implementation  */ 

#include<iostream>
using namespace std;

struct Node{
    int data;
    Node* left;
    Node* right;
};


Node* GetNewNode(int x){
    Node* temp=new Node;
    temp->data=x;
    temp->left=NULL;
    temp->right=NULL;
    return temp;
}

Node* Insert(Node* root,int x){
    if(root==NULL){
        root=GetNewNode(x);
    }
    else if(x<root->data){
        root->left=Insert(root->left,x);
    }
    else{
        root->right=Insert(root->right,x);
    }

    return root;
}

bool Search(Node* root,int x){
    if(root==NULL) return false;
    if(root->data==x) return true;
    else if(x<=root->data)
        return Search(root->left,x);
    else return Search(root->right,x);

}

int main()
{
    Node * root= NULL;  //keeping root as local variable
    int range,x;
    cout<<"how many elements :";
    cin>>range;
    for(int i=0;i<range;i++){
        cout<<"enter element: ";
        cin>>x;
        root=Insert(root,x);
    }
   
    int num;
    cout<<"Enter number to search: ";
    cin>>num;
    if(Search(root,num)==true)
        cout<<num<<" found"<<endl;
    else cout<<num<<" Not found"<<endl;
    return 0;
}

4.2 Finding min and max element in a BST

Runnable Code Snippet_4.2-a – Finding min element in a BST

/* 4.2-a find min element in a BST   */

/*To find min*/
#include<iostream>
using namespace std;

struct Node{
    int data;
    Node* left;
    Node* right;
};

Node* GetNewNode(int x){
    Node* temp=new Node;
    temp->data=x;
    temp->left=NULL;
    temp->right=NULL;
    return temp;
}

Node* Insert(Node* root,int x){
    if(root==NULL){
        root=GetNewNode(x);
    }
    else if(x<root->data){
        root->left=Insert(root->left,x);
    }
    else{
        root->right=Insert(root->right,x);
    }
    return root;
}


//ftn to find minimum of BST
int FindMin(Node* root){
    if(root==NULL){
        cout<<"Empty"<<endl;
        return -1;
    }
    else if(root->left==NULL){
        return root->data;
    }
    else
        return FindMin(root->left); //recursively
}

int main()
{
    Node * root= NULL;  //keeping root as local variable
    int range,x;
    cout<<"how many elements :";
    cin>>range;
    for(int i=0;i<range;i++){
        cout<<"enter element: ";
        cin>>x;
        root=Insert(root,x);
    }

    int minVal=FindMin(root);
    cout<<"Minimum value is : "<<minVal<<endl;

    return 0;
}

Runnable Code Snippet_4.2-b – Finding max element in a BST

/*4.2-b - Finding max element in a BST */

/*To find max*/

#include<iostream>
using namespace std;

struct Node{
    int data;
    Node* left;
    Node* right;
};


Node* GetNewNode(int x){
    Node* temp=new Node;
    temp->data=x;
    temp->left=NULL;
    temp->right=NULL;
    return temp;
}

Node* Insert(Node* root,int x){
    if(root==NULL){
        root=GetNewNode(x);
    }
    else if(x<root->data){
        root->left=Insert(root->left,x);
    }
    else{
        root->right=Insert(root->right,x);
    }
    return root;
}


//ftn to find maximum of BST
int FindMax(Node* root){
    if(root==NULL){
        cout<<"Empty"<<endl;
        return -1;
    }
    else if(root->right==NULL){
        return root->data;
    }
    else
        return FindMax(root->right); //recursively
}

int main()
{
    Node * root= NULL;  //keeping root as local variable
    int range,x;
    cout<<"how many elements :";
    cin>>range;
    for(int i=0;i<range;i++){
        cout<<"enter element: ";
        cin>>x;
        root=Insert(root,x);
    }

    int maxVal=FindMax(root);
    cout<<"Maximum value is : "<<maxVal<<endl;

    return 0;
}

4.3 Finding Height of BST

Runnable Code Snippet_4.3 – Finding Height of BST

/*  4.3 find height of Binary Tree   */
#include<iostream>
using namespace std;

struct Node{
    int data;
    Node* left;
    Node* right;
};


Node* GetNewNode(int x){
    Node* temp=new Node;
    temp->data=x;
    temp->left=NULL;
    temp->right=NULL;
    return temp;
}

Node* Insert(Node* root,int x){
    if(root==NULL){
        root=GetNewNode(x);
    }
    else if(x<root->data){
        root->left=Insert(root->left,x);
    }
    else{
        root->right=Insert(root->right,x);
    }
    return root;
}

int FindHeight(Node* root){
    if(root==NULL)
        return -1;
    return max(FindHeight(root->left),FindHeight(root->right))+1;
}

int main()
{
    Node * root= NULL;  //keeping root as local variable
    int range,x;
    cout<<"how many elements :";
    cin>>range;
    for(int i=0;i<range;i++){
        cout<<"enter element: ";
        cin>>x;
        root=Insert(root,x);
    }
    int height=FindHeight(root);
    cout<<"Height is: "<<height<<endl;

     return 0;
}

4.4 BST traversal – Breadth first, Depth first

Binary Tree Traversal:

  1. Breadth first a.k.a. Level-Order (we implement Queue(FIFO) to traverse)
  2. Depth first
    1. Pre-Order (DLR) ( root- left – right )
    2. In-Order (LDR) (left- root- right)
    3. Post-Order (LRD) (left- right- data)

4.5 Level order traversal (a.k.a Breadth First)

Runnable Code Snippet_4.5– BST traversal – Breadth first – Level Order

/* 4.5 Breadth first  -Level Order*/

#include<iostream>
#include<queue>
using namespace std;

struct Node{
    int data;
    Node* left;
    Node* right;
};


Node* GetNewNode(int x){
    Node* temp=new Node;
    temp->data=x;
    temp->left=NULL;
    temp->right=NULL;
    return temp;
}

Node* Insert(Node* root,int x){
    if(root==NULL){
        root=GetNewNode(x);
    }
    else if(x<root->data){
        root->left=Insert(root->left,x);
    }
    else{
        root->right=Insert(root->right,x);
    }
    return root;
}

//LevelOrder ftn using Queue stl
void LevelOrder(Node* root){
    if(root==NULL) return;
    queue<Node*>Q; //from STL
    Q.push(root);
    //while atleast one discovered node
    while(!Q.empty()){
        Node* current=Q.front();
        cout<<current->data<<" ";
        if(current->left!=NULL) Q.push(current->left);
        if(current->right!=NULL)Q.push(current->right);
        Q.pop(); //removing element at front
    }
}


int main()
{
    Node * root= NULL;  //keeping root as local variable
    int range,x;
    cout<<"how many elements :";
    cin>>range;
    for(int i=0;i<range;i++){
        cout<<"enter element: ";
        cin>>x;
        root=Insert(root,x);
    }

    LevelOrder(root);

    return 0;
}

4.6 Preorder, Inorder and PostOrder traversal

Runnable Code Snippet_4.6 – Preorder(DLR), Inorder (LDR), Postorder(LRD)

/*  4.6 Preorder(DLR), Inorder (LDR), Postorder(LRD)*/

#include<iostream>
using namespace std;

struct Node{
    int data;
    Node* left;
    Node* right;
};

Node* GetNewNode(int x){
    Node* temp=new Node;
    temp->data=x;
    temp->left=NULL;
    temp->right=NULL;
    return temp;
}

Node* Insert(Node* root,int x){
    if(root==NULL){
        root=GetNewNode(x);
    }
    else if(x<root->data){
        root->left=Insert(root->left,x);
    }
    else{
        root->right=Insert(root->right,x);
    }
    return root;
}

//Preorder DLR
void PreOrder(Node* root){
    if(root==NULL) return;
    cout<<root->data<<" ";
    PreOrder(root->left);
    PreOrder(root->right);
}


//Inorder LDR
void Inorder (Node* root){
    if(root==NULL) return;
    Inorder(root->left);
    cout<<root->data<<" ";
    Inorder(root->right);
}

//PostOrder LRD
void PostOrder(Node* root){
    if(root==NULL)return;
    PostOrder(root->left);
    PostOrder(root->right);
    cout<<root->data<<" ";
}

int main()
{
    Node * root= NULL;  //keeping root as local variable
    int range,x;
    cout<<"how many elements :";
    cin>>range;
    for(int i=0;i<range;i++){
        cout<<"enter element: ";
        cin>>x;
        root=Insert(root,x);
    }
    cout<<"Preorder: ";
    PreOrder(root);
    cout<<endl<<"Inorder: ";
    Inorder(root);
    cout<<endl<<"Postorder: ";
    PostOrder(root);
    return 0;
}

4.7 Checking whether a Binary tree is BST

Runnable Code Snippet_4.7 – Check Binary tree is BST 

/* 4.7 - Check given Binary tree is BST */

#include<iostream>
using namespace std; 

struct Node
{
    int data;
    Node* left;
    Node* right;
};
 
Node* GetNewNode(int x){
    Node* temp=new Node;
    temp->data=x;
    temp->left=NULL;
    temp->right=NULL;
    return temp;
}

Node* Insert(Node* root,int x){
    if(root==NULL){
        root=GetNewNode(x);
    }
    else if(x<root->data){
        root->left=Insert(root->left,x);
    }
    else{
        root->right=Insert(root->right,x);
    }
    return root;
}

// Returns true if given tree is BST.
bool isBST(Node* root, Node* l=NULL, Node* r=NULL)
{
    // Base condition
    if (root == NULL)
        return true;
 
    // if left node exist then check it has
    // correct data or not
    if (l != NULL && root->data < l->data)
        return false;
 
    // if right node exist then check it has
    // correct data or not
    if (r != NULL && root->data > r->data)
        return false;
 
    // check recursively for every node.
    return isBST(root->left, l, root) &&
           isBST(root->right, root, r);
}
 
 
/* Driver program to test above functions*/
int main()
{   
	Node * root= NULL; 
    int range,x;
    cout<<"how many elements :";
    cin>>range;
    for(int i=0;i<range;i++){
        cout<<"enter element: ";
        cin>>x;
        root=Insert(root,x);
    }

    if (isBST(root))
        cout << " Above binary tree is a BST...\n";
    else
        cout << "Above binary tree is not a BST..!\n";
 
    return 0;
}

4.8 Deleting a node from BST

Runnable Code Snippet_4.8 – Delete a node from BST

/*  4.8 delete a node from BST   */
#include<iostream>
using namespace std;

struct Node{
    int data;
    Node* left;
    Node* right;
};

Node* GetNewNode(int x){
    Node* temp=new Node;
    temp->data=x;
    temp->left=NULL;
    temp->right=NULL;
    return temp;
}

Node* Insert(Node* root,int x){
    if(root==NULL){
        root=GetNewNode(x);
    }
    else if(x<root->data){
        root->left=Insert(root->left,x);
    }
    else{
        root->right=Insert(root->right,x);
    }
    return root;
}

Node* FindMin(Node* root){
    if(root==NULL){
        cout<<"Empty"<<endl;
        return NULL;
    }
    else if(root->left==NULL){
        return root;
    }
    else
        return FindMin(root->left);
}

//Delete ftn
Node* Delete(Node* root,int data){

    if(root==NULL) return root;
    else if(data<root->data)
        root->left=Delete(root->left,data);
    else if(data>root->data)
        root->right=Delete(root->right,data);
    else{  //we've found the node to be deleted

        //case 1:No child
        if(root->left==NULL && root->right==NULL){
            delete root;
            root=NULL; //to avoid dangling pointer
        }

        //case 2: One child
        else if(root->left==NULL){
            Node* temp=root;
            root=root->right;
            delete temp;
        }
        else if(root->right==NULL){
            Node* temp=root;
            root=root->left;
            delete temp;
        }

        //case 3: 2 children
        else{
            Node* temp=FindMin(root->right);
            root->data=temp->data;
            root->right=Delete(root->right,temp->data);
        }
    }

    return root;  //important
}

//to traverse and print
void InOrder(Node* root){
    if(root==NULL) return;
    InOrder(root->left);
    cout<<root->data<<" ";
    InOrder(root->right);
}

int main()
{
    Node * root= NULL;  //keeping root as local variable
    int range,x;
    cout<<"how many elements :";
    cin>>range;
    for(int i=0;i<range;i++){
        cout<<"enter element: ";
        cin>>x;
        root=Insert(root,x);
    }

    InOrder(root);

    Delete(root,10);
    cout<<endl;
    InOrder(root);
    return 0;
}

We covered Tree ADT, Binary Search Tree(BST) implementation, Finding min and max element in a BST, Finding height of BST, BST traversal Breadth first, Depth first, Level order traversal-Preorder, Inorder and PostOrder traversal, Checking whether a Binary tree is BST, Deleting a node from BST concepts. In our next module we will discuss Search and Sort Algorithms.

Please follow the blog to stay updated with the upcoming modules.

love,

<R.S>

For Complete Sourcecode visit my Github repo: Link provided in the final module

Rating: 3.5 out of 5.
<< Prev
Next >>

RS-codes

2 thoughts on “Data Structures & Algorithms – Tree”

  1. Pingback: Data Structures & Algorithms – Queue – RS-codes
  2. Pingback: Data Structures & Algorithms – Search and Sort Algorithm – RS-codes

Leave a comment

Design a site like this with WordPress.com
Get started