Random Quote
Random Quotes
Categories
- A ll Codes (310)
- ACM (221)
- ACM Technique (18)
- ACM-ICPC (57)
- Adhoc/Brute Force (3)
- Algorithm (83)
- Algo Unsolved (3)
- Asymptotic Notation (3)
- Geometry (2)
- Graph (6)
- All Pair Shortest Path (1)
- BFS (1)
- DFS (1)
- Single Source Shortest Path (2)
- Bellman Ford (1)
- Dijkstra (1)
- Topological Sort (1)
- Number Theory (6)
- Euler GCD (1)
- GCD (1)
- LCM (1)
- Prime factorization (1)
- Sieve of Erastosthenes (1)
- Trial Division (1)
- Recursion (3)
- Fibonacci (1)
- Tower of Hanoi (1)
- Searching (3)
- Binary Search (2)
- Linear Search (1)
- Sorting (13)
- Bubble Sort (1)
- Bucket Sort (1)
- Counting Sort (1)
- Heap Sort (1)
- Insertion Sort (1)
- Merge Sort (3)
- Quicksort (2)
- Radix Sort (1)
- Selection Sort (3)
- Tree (6)
- AVL Tree (1)
- B+ Tree (1)
- Binary Search Tree (4)
- Competitive Programming (1)
- Data Structure (6)
- Linked List (1)
- Queue (2)
- Circular Queue (1)
- Stack (1)
- Future Reference (1)
- Problem Solution (101)
- Codeforces (3)
- DevSkill (1)
- HackerEarth (17)
- HackerRank (4)
- Lightoj (2)
- SPOJ (1)
- Unsolved (1)
- URI Online Judge (34)
- UVa (18)
- Programming Contest (2)
- Programming Problem Solving (18)
- CS Courses (141)
- Art of Effective Living (1)
- Artificial Intelligence (12)
- Assembly Language (3)
- Compiler Design (1)
- Computer Architecture (3)
- Data Communication (1)
- Data Mining (10)
- WEKA (2)
- Database (10)
- SQL (8)
- Digital Image Processing (5)
- Embedded Systems (2)
- Arduino (2)
- Games Development (1)
- Graphics (9)
- OpenGL (7)
- Mathematics (25)
- Numerical Method (18)
- Bisection Method (4)
- Numerical Method (18)
- Microprocessor (1)
- OOP (44)
- Operating System (11)
- Bash/Shell Scripting (7)
- CPU Scheduling (1)
- Simulation and Modelling (1)
- Web Engineering (1)
- Experience (3)
- Events (1)
- Food Review (1)
- Travel (1)
- Fitness (15)
- Body Transformation (2)
- Bodybuilding (7)
- Cycling (2)
- Fat Loss (2)
- Fitness Motivation (5)
- Health (2)
- Mental Health (1)
- My Gym (2)
- My Life Chart (3)
- My Life Style (3)
- Weight loss (1)
- Graphics Design (1)
- Photoshop (1)
- HigherStudy (72)
- EducationUSA (2)
- English Learning (9)
- Pronunciation (3)
- German Learning (18)
- Germany (2)
- Grammar (7)
- GRE (17)
- IELTS (26)
- Handwriting Improvement (1)
- Listening (4)
- Reading (1)
- Speaking (2)
- Writing Task (3)
- TOEFL (2)
- HTML/CSS (1)
- Job (43)
- CSE (2)
- CV/Resume (4)
- Interview (22)
- Fresher/Intern (1)
- Java (5)
- Masters of Science (1)
- Introductory Data Analysis(IDA) (1)
- Excel (1)
- Introductory Data Analysis(IDA) (1)
- MSSQL (3)
- Stored Procedures (1)
- T-SQL (1)
- Open Source (6)
- Linux (4)
- Ubuntu 15.04 (1)
- Ubuntu 18.04 (1)
- Ubuntu14.04 (1)
- Ubuntu (2)
- Linux (4)
- Philosophy of Life (163)
- Learning (1)
- Life (9)
- Life Motivation (122)
- Business/Money (5)
- Career/Earning (10)
- Depression (3)
- Fearless Motivation (1)
- Life Quotes (2)
- Life Story/Journey (1)
- Passion (1)
- People Skill/Networking (14)
- Stress (2)
- Study Motivation (57)
- Success Hacks (73)
- Healthy Habit (15)
- Never Quit (35)
- Patience (22)
- Social Skills/Communicative Skills (5)
- Time Management (4)
- Life Productivity (10)
- Life Rules (3)
- Life Skills (3)
- Lifefact (3)
- Lifelessons (6)
- Lifestyle (1)
- Love (8)
- Motivation (16)
- Motivational Posts (5)
- Music (4)
- Poems (1)
- Love (1)
- Poetry (1)
- Ramadan (1)
- Romance (4)
- Sadness (2)
- Sarcasm (2)
- Thoughts (2)
- Pore Abar Bujhbo (8)
- Presentation (8)
- Programming (316)
- Language (288)
- C (152)
- Array (24)
- C library function (3)
- C Refresh (106)
- Function (17)
- logic (1)
- Logic Logic (4)
- Logics (1)
- Memory Management (1)
- Pointer (19)
- String (21)
- Structured Programming (1)
- C# (40)
- C++ (35)
- Vector (1)
- Java (44)
- Javascript (1)
- PHP (18)
- Python (13)
- C (152)
- Language (288)
- Project (2)
- Project Report (1)
- Research (49)
- BigData (3)
- Data Science (14)
- Machine Learning (23)
- Natural Language Processing(NLP) (5)
- Plagiarism Checker (1)
- Research Papers (3)
- Research Topic (1)
- Statistics (3)
- Sentiment Analysis (3)
- Software Development (80)
- .NET (34)
- Xamarin (1)
- Android (10)
- ASP.NET (10)
- Debate (2)
- Design Pattern (3)
- Laravel (4)
- Object Notation (3)
- Regex (2)
- Software Development Life Cycle(SDLC) (4)
- Training (9)
- LICT (9)
- unity3d (1)
- Version Control/SVN (4)
- XML (1)
- .NET (34)
- Tech Tips (21)
- Desktop (1)
- Fix (1)
- Laptop (1)
- Laptop(ল্যাপটপ) (1)
- HP (1)
- Techie Talk (15)
- Tech Debate (2)
- VPS (2)
- Uncategorized (35)
- University Life (4)
- 11th semester (1)
- 7th semester (1)
- 9th semester (1)
- Web Links (1)
- বাংলা (10)
- অবজেক্ট ওরিয়েন্টেড প্রোগ্রামিং (1)
- রিসার্চ (1)
- সি প্রোগ্রামিং (2)
- হার্ডডিস্ক পার্টিশান (1)
-
Recent Comments
- ijazbesant on Become a Software Engineer in PHP platform
- zakilive on OOPs ! অবজেক্ট ওরিয়েন্টেড প্রোগ্রামিং কনসেপ্ট এবং তার সূচনা :D
- Hasibul Hasan on OOPs ! অবজেক্ট ওরিয়েন্টেড প্রোগ্রামিং কনসেপ্ট এবং তার সূচনা :D
- Rezaul Islam on Some Android Links that May Help
- chris woodward on Project UX design for Java Balloon Shooter Game in 4th semester
Category Archives: Tree
Binary Search Tree: Successor in Inorder Traversal
code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
/* 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"; } |
https://www.youtube.com/watch?v=5cPbNCrdotA
Posted in Binary Search Tree, Tree
Delete a node in Binary Search Tree
https://www.youtube.com/watch?v=gcULXE7ViZw
code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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"; } |
Posted in Binary Search Tree, Tree
Traversal in Binary Search Tree
Height of a binary tree:
https://www.youtube.com/watch?v=_pnqMz5nrRs
Level Order BFS in Binary Search Tree:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#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:
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
#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:
1 2 3 |
Preorder: M B A C Q Z Inorder: A B C M Q Z Postorder: A C B Z Q M |
Posted in Binary Search Tree, Tree
Binary Search Tree
youtube :
https://www.youtube.com/watch?v=COZK7NATh4k
code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#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; } |
Posted in Binary Search Tree, Tree