Home Trees Write an algorithm to delete a complete binary tree

Write an algorithm to delete a complete binary tree

by nikoo28
0 comment

Question: Given the root pointer to a binary tree, delete the binary tree

Input: Sample Tree (Pointer to node 1 is given).
sample_tree

To delete a tree we must traverse all the nodes of the tree and delete them one by one. So which traversal should we use ? Inorder, Pre-order, Post-order or Level Order Traversal ?

Before deleting he parent node, we should delete its child node first. We can therefore use post order traversal as it does the work without storing anything. We can delete three with other traversals also but the space complexity will increase.

For the above given tree, the tree will be deleted in the order :- 7, 9, 5, 4, 2, 3, 1

#include<stdio.h>
#include<malloc.h>

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

struct binaryTreeNode * deleteBinaryTree(struct binaryTreeNode * root)
{
	if(root == NULL)
		return NULL;
	
	// Delete the sub-trees first
	root -> left = deleteBinaryTree(root -> left);
	root -> right = deleteBinaryTree(root -> right);
	
	// Delete the current node only after deleting sub-trees
	free(root);
	
	return NULL;
}

Time Complexity:- O(n)
Space Complexity:- O(n)

Ideone link for running program:- http://ideone.com/pxE5EA

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More