Given a binary tree, write an efficient algorithm to delete entire binary tree.
The program should de-allocate every single node present in the tree, not just change reference of the root node to null.
The idea is to traverse the tree in post-order fashion and delete left and right subtree of a node before deleting the node itself. Note that we cannot traverse the tree in preorder or inorder fashion as we can’t delete a parent before deleting its children’s.
C++ implementation –
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // Recursive function to delete given binary tree void deleteBinaryTree(Node* &root) { // Base case: empty tree if (root == nullptr) return; // delete left and right subtree first (Postorder) deleteBinaryTree(root->left); deleteBinaryTree(root->right); // After deleting left and right sub-tree, delete the current node delete root; // set root as NULL before returning root = nullptr; } |
Iterative solution –
In iterative version, we perform level order traversal of the tree. The idea is to delete each node in the queue one by one after pushing their children to the queue. Note that we’re deleting a parent here before deleting its children’s as we’re pushing them into the queue and they will be processed and deleted afterwards.
C++ implementation –
|
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 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // Iterative function to delete given binary tree void deleteBinaryTree(Node* &root) { // empty tree if (root == nullptr) return; // create an empty queue and enqueue root node queue<Node*> queue; queue.push(root); Node *front = nullptr; // run till queue is not empty while (!queue.empty()) { // delete each node in the queue one by one after pushing their // non-empty left and right child to the queue front = queue.front(); queue.pop(); if (front->left) queue.push(front->left); if (front->right) queue.push(front->right); // Important - delete front node ONLY after enqueuing its children delete front; } // set root as NULL before returning root = nullptr; } |
The time complexity of both recursive and iterative solution is O(n).
Thanks for reading.
Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply