Category Archives: Tree

code:

/* C++ program to find Inorder successor in a BST */
#include<bits/stdc++.h>
using namespace std;
struct Node {
	int data;
	struct Node *left;
	struct Node *right;
};

//Function to find some data in the tree
Node* Find(Node*root, int data) {
	if(root == NULL) return NULL;
	else if(root->data == data) return root;
	else if(root->data < data) return Find(root->right,data);
	else return Find(root->left,data);
}

//Function to find Node with minimum value in a BST
struct Node* FindMin(struct Node* root) {
	if(root == NULL) return NULL;
	while(root->left != NULL)
		root = root->left;
	return root;
}

//Function to find Inorder Successor in a BST
struct Node* Getsuccessor(struct Node* root,int data) {
	// Search the Node - O(h)
	struct Node* current = Find(root,data);
	if(current == NULL) return NULL;
	if(current->right != NULL) {  //Case 1: Node has right subtree
		return FindMin(current->right); // O(h)
	}
	else {   //Case 2: No right subtree  - O(h)
		struct Node* successor = NULL;
		struct Node* ancestor = root;
		while(ancestor != current) {
			if(current->data < ancestor->data) {
				successor = ancestor; // so far this is the deepest node for which current node is in left
				ancestor = ancestor->left;
			}
			else
				ancestor = ancestor->right;
		}
		return successor;
	}
}

//Function to visit nodes in Inorder
void Inorder(Node *root) {
	if(root == NULL) return;

	Inorder(root->left);       //Visit left subtree
	printf("%d ",root->data);  //Print data
	Inorder(root->right);      // Visit right subtree
}

// Function to Insert Node in a Binary Search Tree
Node* Insert(Node *root,char data) {
	if(root == NULL) {
		root = new Node();
		root->data = data;
		root->left = root->right = NULL;
	}
	else if(data <= root->data)
		root->left = Insert(root->left,data);
	else
		root->right = Insert(root->right,data);
	return root;
}

int main() {
	/*Code To Test the logic
	  Creating an example tree
	                    5
			   / \
			  3   10
			 / \   \
			1   4   11
    */
	Node* root = NULL;
	root = Insert(root,5); 
        root = Insert(root,10);
	root = Insert(root,3); 
        root = Insert(root,4);
	root = Insert(root,1); 
        root = Insert(root,11);

	//Print Nodes in Inorder
	cout<<"Inorder Traversal: ";
	Inorder(root);
	cout<<"\n";

	// Find Inorder successor of some node.
	struct Node* successor = Getsuccessor(root,1);
	if(successor == NULL) cout<<"No successor Found\n";
	else
    cout<<"Successor is "<<successor->data<<"\n";
}

/* C++ program to find Inorder successor in a BST */

#include<bits/stdc++.h>

using namespace std;

struct Node {

int data;

struct Node *left;

struct Node *right;

};

//Function to find some data in the tree

Node* Find(Node*root, int data) {

if(root == NULL) return NULL;

else if(root->data == data) return root;

else if(root->data < data) return Find(root->right,data);

else return Find(root->left,data);

}

//Function to find Node with minimum value in a BST

struct Node* FindMin(struct Node* root) {

if(root == NULL) return NULL;

while(root->left != NULL)

root = root->left;

return root;

}

//Function to find Inorder Successor in a BST

struct Node* Getsuccessor(struct Node* root,int data) {

// Search the Node - O(h)

struct Node* current = Find(root,data);

if(current == NULL) return NULL;

if(current->right != NULL) { //Case 1: Node has right subtree

return FindMin(current->right); // O(h)

}

else { //Case 2: No right subtree - O(h)

struct Node* successor = NULL;

struct Node* ancestor = root;

while(ancestor != current) {

if(current->data < ancestor->data) {

successor = ancestor; // so far this is the deepest node for which current node is in left

ancestor = ancestor->left;

}

else

ancestor = ancestor->right;

}

return successor;

}

//Function to visit nodes in Inorder

void Inorder(Node *root) {

if(root == NULL) return;

Inorder(root->left); //Visit left subtree

printf("%d ",root->data); //Print data

Inorder(root->right); // Visit right subtree

}

// Function to Insert Node in a Binary Search Tree

Node* Insert(Node *root,char data) {

if(root == NULL) {

root = new Node();

root->data = data;

root->left = root->right = NULL;

}

else if(data <= root->data)

root->left = Insert(root->left,data);

else

root->right = Insert(root->right,data);

return root;

}

int main() {

/*Code To Test the logic

Creating an example tree

/ \

3 10

/ \ \

1 4 11

Node* root = NULL;

root = Insert(root,5);

root = Insert(root,10);

root = Insert(root,3);

root = Insert(root,4);

root = Insert(root,1);

root = Insert(root,11);

//Print Nodes in Inorder

cout<<"Inorder Traversal: ";

Inorder(root);

cout<<"\n";

// Find Inorder successor of some node.

struct Node* successor = Getsuccessor(root,1);

if(successor == NULL) cout<<"No successor Found\n";

else

cout<<"Successor is "<<successor->data<<"\n";

}

https://www.youtube.com/watch?v=5cPbNCrdotA

Leave a comment

Posted in Binary Search Tree, Tree

Delete a node in Binary Search Tree

Posted on July 5, 2017 | Leave a comment

https://www.youtube.com/watch?v=gcULXE7ViZw

code:

#include<bits/stdc++.h>
using namespace std;

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

Node* FindMin(Node* root)
{
    while(root->left!=NULL)
        root=root->left;
    return root;
}

//Function to search a delete value from tree
struct Node* Delete(struct 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{
        //case 1: No child
        if(root->left==NULL && root->right==NULL)
        {
            delete root;
            root=NULL;
        }
        //case 2: one child
        else if(root->left==NULL)
        {
            struct Node* temp=root;
            root=root->right;
            delete temp;
        }
        else if(root->right==NULL)
        {
            struct Node* temp=root;
            root=root->left;
            delete temp;
        }
        //case 3: 2 children
        else{
            struct Node * temp=FindMin(root->right);
            root->data=temp->data;
            root->right=Delete(root->right, temp->data);
        }

    }
return root;
}

//function to visit nodes in inorder
void Inorder(Node* root)
{
    if(root==NULL)
          return;
    Inorder(root->left); //visit left subtree
    printf("%d ",root->data); //print data
    Inorder(root->right); //visit right subtree
}


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

int main()
{
    Node *root=NULL;
    root=Insert(root,5);
    root=Insert(root,10);
    root=Insert(root,3);
    root=Insert(root,4);
    root=Insert(root,1);
    root=Insert(root,11);

    root=Delete(root,5);

    //Print Nodes in Inorder
    cout<<"Inorder: ";
    Inorder(root);
    cout<<"\n";

}

100

101

#include<bits/stdc++.h>

using namespace std;

struct Node{

int data;

struct Node* left;

struct Node* right;

};

Node* FindMin(Node* root)

{

while(root->left!=NULL)

root=root->left;

return root;

}

//Function to search a delete value from tree

struct Node* Delete(struct 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{

//case 1: No child

if(root->left==NULL && root->right==NULL)

{

delete root;

root=NULL;

}

//case 2: one child

else if(root->left==NULL)

{

struct Node* temp=root;

root=root->right;

delete temp;

}

else if(root->right==NULL)

{

struct Node* temp=root;

root=root->left;

delete temp;

}

//case 3: 2 children

else{

struct Node * temp=FindMin(root->right);

root->data=temp->data;

root->right=Delete(root->right, temp->data);

}

return root;

}

//function to visit nodes in inorder

void Inorder(Node* root)

{

if(root==NULL)

return;

Inorder(root->left); //visit left subtree

printf("%d ",root->data); //print data

Inorder(root->right); //visit right subtree

}

Node* Insert(Node *root, char data)

{

if(root==NULL)

{

root=new Node();

root->data=data;

root->left=root->right=NULL;

}

else if(data<=root->data)

root->left=Insert(root->left,data);

else

root->right=Insert(root->right,data);

return root;

}

int main()

{

Node *root=NULL;

root=Insert(root,5);

root=Insert(root,10);

root=Insert(root,3);

root=Insert(root,4);

root=Insert(root,1);

root=Insert(root,11);

root=Delete(root,5);

//Print Nodes in Inorder

cout<<"Inorder: ";

Inorder(root);

cout<<"\n";

}

Leave a comment

Posted in Binary Search Tree, Tree

Traversal in Binary Search Tree

Posted on July 4, 2017 | Leave a comment

Height of a binary tree:

https://www.youtube.com/watch?v=_pnqMz5nrRs

Level Order BFS in Binary Search Tree:

#include<bits/stdc++.h>
#include<queue>
using namespace std;

struct Node
{
    char data;
    Node *left;
    Node *right;
};
//Function to print nodes in a binary tree in level order
void LevelOrder(Node *root)
{
    if(root==NULL)
        return;
    queue<Node*> Q;
    Q.push(root);
    //while there is at least one discovered node
    while(!Q.empty())
    {
        Node* current=Q.front();
        Q.pop();
        cout<<current->data<<" ";
        if(current->left!=NULL)
            Q.push(current->left);
        if(current->right!=NULL)
            Q.push(current->right);
    }
}
//Function to insert node in a binary search tree
Node* Insert(Node *root, char data)
{
    if(root==NULL)
    {
        root=new Node();
        root->data=data;
        root->left=root->right=NULL;
    }
    else if(data<=root->data)
        root->left=Insert(root->left,data);
    else
        root->right=Insert(root->right,data);
    return root;
}
int main()
{

    //creating an example tree

    Node *root=NULL;
    root=Insert(root,'M');
    root=Insert(root,'B');
    root=Insert(root,'Q');
    root=Insert(root,'Z');
    root=Insert(root,'A');
    root=Insert(root,'C');
    LevelOrder(root);
}

#include<bits/stdc++.h>

#include<queue>

using namespace std;

struct Node

{

char data;

Node *left;

Node *right;

};

//Function to print nodes in a binary tree in level order

void LevelOrder(Node *root)

{

if(root==NULL)

return;

queue<Node*> Q;

Q.push(root);

//while there is at least one discovered node

while(!Q.empty())

{

Node* current=Q.front();

Q.pop();

cout<<current->data<<" ";

if(current->left!=NULL)

Q.push(current->left);

if(current->right!=NULL)

Q.push(current->right);

}

//Function to insert node in a binary search tree

Node* Insert(Node *root, char data)

{

if(root==NULL)

{

root=new Node();

root->data=data;

root->left=root->right=NULL;

}

else if(data<=root->data)

root->left=Insert(root->left,data);

else

root->right=Insert(root->right,data);

return root;

}

int main()

{

//creating an example tree

Node *root=NULL;

root=Insert(root,'M');

root=Insert(root,'B');

root=Insert(root,'Q');

root=Insert(root,'Z');

root=Insert(root,'A');

root=Insert(root,'C');

LevelOrder(root);

}

output:

M B Q A C Z

1	M B Q A C Z

https://www.youtube.com/watch?v=gm8DUJJhmY4&index=34&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P
DFS in Preorder, Inorder, Postorder:

#include<bits/stdc++.h>
#include<queue>
using namespace std;

struct Node
{
    char data;
    Node *left;
    Node *right;
};
//Function to print nodes in a binary tree in level order
void Preorder(struct Node* root){

    if(root==NULL)
        return;
    printf("%c ",root->data);//print data
    Preorder(root->left); //visit left subtree
    Preorder(root->right); //Visit right subtree
}

//function to visit nodes in Inorder
void Inorder(Node* root)
{
    if(root==NULL)
        return;
    Inorder(root->left); //Visit left subtree
    printf("%c ",root->data); //Print  data
    Inorder(root->right); //Visit right subtree
}

void Postorder(Node* root)
{
    if(root==NULL)
        return;
    Postorder(root->left); //visit left subtree
    Postorder(root->right); //visit right subtree
    printf("%c ",root->data); //print data


}


//Function to insert node in a binary search tree
Node* Insert(Node *root, char data)
{
    if(root==NULL)
    {
        root=new Node();
        root->data=data;
        root->left=root->right=NULL;
    }
    else if(data<=root->data)
        root->left=Insert(root->left,data);
    else
        root->right=Insert(root->right,data);
    return root;
}
int main()
{

    //creating an example tree

    Node *root=NULL;
    root=Insert(root,'M');
    root=Insert(root,'B');
    root=Insert(root,'Q');
    root=Insert(root,'Z');
    root=Insert(root,'A');
    root=Insert(root,'C');

    //Print nodes in preorder
    cout<<"Preorder: ";
    Preorder(root);
    cout<<endl;
    //Print nodes in in inorder
    cout<<"Inorder:  ";
    Inorder(root);
    cout<<endl;
    //Print Nodes in postorder
    cout<<"Postorder: ";
    Postorder(root);
    cout<<endl;
    return 0;
}

#include<bits/stdc++.h>

#include<queue>

using namespace std;

struct Node

{

char data;

Node *left;

Node *right;

};

//Function to print nodes in a binary tree in level order

void Preorder(struct Node* root){

if(root==NULL)

return;

printf("%c ",root->data);//print data

Preorder(root->left); //visit left subtree

Preorder(root->right); //Visit right subtree

}

//function to visit nodes in Inorder

void Inorder(Node* root)

{

if(root==NULL)

return;

Inorder(root->left); //Visit left subtree

printf("%c ",root->data); //Print data

Inorder(root->right); //Visit right subtree

}

void Postorder(Node* root)

{

if(root==NULL)

return;

Postorder(root->left); //visit left subtree

Postorder(root->right); //visit right subtree

printf("%c ",root->data); //print data

}

//Function to insert node in a binary search tree

Node* Insert(Node *root, char data)

{

if(root==NULL)

{

root=new Node();

root->data=data;

root->left=root->right=NULL;

}

else if(data<=root->data)

root->left=Insert(root->left,data);

else

root->right=Insert(root->right,data);

return root;

}

int main()

{

//creating an example tree

Node *root=NULL;

root=Insert(root,'M');

root=Insert(root,'B');

root=Insert(root,'Q');

root=Insert(root,'Z');

root=Insert(root,'A');

root=Insert(root,'C');

//Print nodes in preorder

cout<<"Preorder: ";

Preorder(root);

cout<<endl;

//Print nodes in in inorder

cout<<"Inorder: ";

Inorder(root);

cout<<endl;

//Print Nodes in postorder

cout<<"Postorder: ";

Postorder(root);

cout<<endl;

return 0;

}

output:

Preorder: M B A C Q Z
Inorder:  A B C M Q Z
Postorder: A C B Z Q M

Preorder: M B A C Q Z

Inorder: A B C M Q Z

Postorder: A C B Z Q M

Leave a comment

Posted in Binary Search Tree, Tree

Binary Search Tree

Posted on July 4, 2017 | Leave a comment

youtube :

https://www.youtube.com/watch?v=COZK7NATh4k

code:

#include<iostream>
using namespace std;
//Definition of Node for Binary search tree
struct BstNode
{
    int data;
    BstNode* left;
    BstNode* right;
};
//Function to create new Node in heap
BstNode* GetNewNode(int data)
{
    BstNode* newNode=new BstNode();
    newNode->data=data;
    newNode->left=newNode->right=NULL;
    return newNode;
}
//To search an element in BST return true if element is found
bool Search(BstNode* root, int data)
{
    if(root==NULL)
        return false;
    else if(root->data==data)
        return true;
    else if(data<=root->data)
        return Search(root->left,data);
    else
        return Search(root->right,data);
}
//TO insert data in BST, return address of root node
BstNode* Insert(BstNode* root, int data)
{
    if(root==NULL) //empty tree
    {
        root=GetNewNode(data);
    }
    //if data to be inserted is lesser, insert it in left subtree
    else if(data<=root->data)
    {
        root->left=Insert(root->left,data);
    }
    //else, insert in right subtree
    else
    {
        root->right=Insert(root->right,data);
    }
    return root;
}

int main()
{
    BstNode* root=NULL;//creating an empty tree
    /* Code to test the logic */
    root=Insert(root,15);
    root=Insert(root,10);
    root=Insert(root,20);
    root=Insert(root,25);
    root=Insert(root,8);
    root=Insert(root,12);
    //asking user to enter a number
    int number;
    cout<<"Enter number to be searched:\n";
    cin>>number;
    //If number is found, print "FOUND"
    if(Search(root,number)==true)
        cout<<"Found\n";
    else
        cout<<"Not Found\n";
    return 0;
}

#include<iostream>

using namespace std;

//Definition of Node for Binary search tree

struct BstNode

{

int data;

BstNode* left;

BstNode* right;

};

//Function to create new Node in heap

BstNode* GetNewNode(int data)

{

BstNode* newNode=new BstNode();

newNode->data=data;

newNode->left=newNode->right=NULL;

return newNode;

}

//To search an element in BST return true if element is found

bool Search(BstNode* root, int data)

{

if(root==NULL)

return false;

else if(root->data==data)

return true;

else if(data<=root->data)

return Search(root->left,data);

else

return Search(root->right,data);

}

//TO insert data in BST, return address of root node

BstNode* Insert(BstNode* root, int data)

{

if(root==NULL) //empty tree

{

root=GetNewNode(data);

}

//if data to be inserted is lesser, insert it in left subtree

else if(data<=root->data)

{

root->left=Insert(root->left,data);

}

//else, insert in right subtree

else

{

root->right=Insert(root->right,data);

}

return root;

}

int main()

{

BstNode* root=NULL;//creating an empty tree

/* Code to test the logic */

root=Insert(root,15);

root=Insert(root,10);

root=Insert(root,20);

root=Insert(root,25);

root=Insert(root,8);

root=Insert(root,12);

//asking user to enter a number

int number;

cout<<"Enter number to be searched:\n";

cin>>number;

//If number is found, print "FOUND"

if(Search(root,number)==true)

cout<<"Found\n";

else

cout<<"Not Found\n";

return 0;

}

Leave a comment

Posted in Binary Search Tree, Tree

Category Archives: Tree

AVL Tree

B+ Tree

Binary Search Tree: Successor in Inorder Traversal

Delete a node in Binary Search Tree

Traversal in Binary Search Tree

Binary Search Tree

Categories

Recent Comments

About Me & MyBlog

Caution and Tips:

My Facebook

Recent Posts

Archives

Category Archives: Tree

AVL Tree

B+ Tree

Binary Search Tree: Successor in Inorder Traversal

Delete a node in Binary Search Tree

Traversal in Binary Search Tree

Binary Search Tree

Categories

Recent Comments

About Me & MyBlog

Caution and Tips:

My Facebook

Recent Posts

Tags

Archives