Binary tree operations
Tue Jun 06 2023 00:50:56 GMT+0000 (Coordinated Universal Time)
#include <iostream> #include <queue> using namespace std; // Binary Tree Node struct Node { int data; Node* left; Node* right; }; // Function to create a new node Node* createNode(int value) { Node* newNode = new Node(); if (!newNode) { cout << "Memory error\n"; return NULL; } newNode->data = value; newNode->left = newNode->right = NULL; return newNode; } // Function to insert a node in the tree using level-order traversal Node* levelOrderInsertion(Node* root, int value) { if (root == NULL) { root = createNode(value); return root; } queue<Node*> q; q.push(root); while (!q.empty()) { Node* temp = q.front(); q.pop(); if (temp->left == NULL) { temp->left = createNode(value); break; } else { q.push(temp->left); } if (temp->right == NULL) { temp->right = createNode(value); break; } else { q.push(temp->right); } } return root; } // Depth-First Search (DFS) Traversal void dfsTraversal(Node* root) { if (root == NULL) { return; } cout << root->data << " "; dfsTraversal(root->left); dfsTraversal(root->right); } // Breadth-First Search (BFS) Traversal void bfsTraversal(Node* root) { if (root == NULL) { return; } queue<Node*> q; q.push(root); while (!q.empty()) { Node* temp = q.front(); q.pop(); cout << temp->data << " "; if (temp->left != NULL) { q.push(temp->left); } if (temp->right != NULL) { q.push(temp->right); } } } // Function to delete leaf nodes using level-order traversal Node* levelOrderDeletion(Node* root) { if (root == NULL) { return NULL; } queue<Node*> q; q.push(root); while (!q.empty()) { Node* temp = q.front(); q.pop(); if (temp->left != NULL) { if (temp->left->left == NULL && temp->left->right == NULL) { delete temp->left; temp->left = NULL; } else { q.push(temp->left); } } if (temp->right != NULL) { if (temp->right->left == NULL && temp->right->right == NULL) { delete temp->right; temp->right = NULL; } else { q.push(temp->right); } } } return root; } int main() { Node* root = NULL; // Level-order insertion root = levelOrderInsertion(root, 1); root = levelOrderInsertion(root, 2); root = levelOrderInsertion(root, 3); root = levelOrderInsertion(root, 4); root = levelOrderInsertion(root, 5); cout << "DFS Traversal: "; dfsTraversal(root); cout << endl; cout << "BFS Traversal: "; bfsTraversal(root); cout << endl; // Level-order deletion of leaf nodes root = levelOrderDeletion(root); cout << "DFS Traversal after deletion: "; dfsTraversal(root); cout << endl; return 0; }
Comments