Binary Search Tree : Bottom up approach to problems

Introduction

In Binary Search Tree, there is a class of problems which have solutions with similar structure.

These problems involve deletion of complete BST, mirroring a BST, replacing parent node with sum of children etc. In this post we would discuss the structure of the solution and their execution in run time in detail. Once this strategy is mastered, most of the BST problems can be solved easily.

Problem statement

1. Delete a given Binary Search Tree

2. Mirror a give Binary Search Tree i.e. Left child should become right and right should become left.

3. Replace the value of a node with sum of its children nodes.

Analysis

Problem 1 :Delete a BST

To delete a binary search tree, we start with leaf nodes. Once all leaf nodes are deleted, we move to upper layer which in turn would have become leaf nodes now. We continue to do so till the time we reach root node and then delete root node.

Algorithm

1. Start with root node.
2. If root is null, return.
3. Check if there is left child, delete the sub tree with root as left child.
4. Check if there is right child, delete the sub tree with root as right child.
5. Delete the root node.

Complete code

void delete_BST(Node *root){


        if(!root)
                return ;

        delete_BST(root->left);
        delete_BST(root->right);

        free(root);

}

Problem 2 : Mirror a given BST

To mirror a BST, we need to again start from the leaves. We first swap the lower most nodes, then move up till  the root.

Algorithm

1. Start with root node.
2. If root is null return
3. If there is left child, then mirror the left sub tree.
4. If there is right child, then mirror the right sub tree.
5. Swap left and right child.

Complete code

void delete_BST(Node *root){

        if(!root)
                return ;

        delete_BST(root->left);
        delete_BST(root->right);

        free(root);

}

Problem 3 : Replace a node with sum of its children

This problem requires clarification. Consider a tree as below.

Output should be as

This problem again demands that left and right tree should be solved first and then the root.

Algorithm

1. Start with root node.
2. If root is null return zero.
3. If there is left child, replace the left child with sum of its children.
4. If there is right child, replace the right child with sum of its children.
5. Replace the root with sum of its right and left child.

Complete code

int replace_sum(Node *node){

        if (node == NULL)
                return 0;

        int left_sum =  replace_sum(node->left);
        int right_sum = replace_sum(node->right);

        node->value = left_sum + right_sum;

        return node->value;
}

If we see closely, all three codes are very similar in structure. We first put the termination condition, solve the given problem for the left sub tree, solve the given problem for right sub tree and then do the processing to update the root.

Execution

For Problem 1 : Delete a given BST

Considering node 6
Considering node 3
Considering node 2

Deleted left sub-tree of  2
Deleted right sub-tree of  2
Deleting node  2

Deleted left sub-tree of  3
Considering node 5
Deleted left sub-tree of  5
Deleted right sub-tree of  5
Deleting node  5
Deleted right sub-tree of  3
Deleting node  3
Deleted left sub-tree of  6 <<<<<<<Left sub tree of 6 deleted
Considering node 7         <<<<<< Right sub tree being deleted
Deleted left sub-tree of  7
Considering node 9
Deleted left sub-tree of  9
Deleted right sub-tree of  9
Deleting node  9
Deleted right sub-tree of  7
Deleting node  7
Deleted right sub-tree of  6
Deleting node  6 <<<<<<<<<<<<<<<<< Now root is being deleted


Problem 2 : Mirror of a given BST

Considering node 6
Considering node 3
Considering node 2
Swapped left and right child of 2
Left sub-tree of 3 rooted at  2 mirrored
Considering node 5
Swapped left and right child of 5
Right sub-tree of 3 rooted at  5 mirrored 
Swapped left and right child of 3
Left sub-tree of 6 rooted at  3 mirrored  <<<<Left sub tree mirrored
Considering node 7
Considering node 9
Swapped left and right child of 9
Right sub-tree of 7 rooted at  9 mirrored 
Swapped left and right child of 7
Right sub-tree of 6 rooted at  7 mirrored <<<<<Right sub tree mirrored

Swapped left and right child of 6 <<<right and left swapped.

Problem 3 :  Replace by sum of children node 

Considering node 10
Considering node 8
Considering node 6
Sum of left sub-tree of  6: 0
  Sum of right sub-tree of  6: 0
  Sum of left sub-tree of  8: 6
  Considering node 9
Sum of left sub-tree of  9: 0
  Sum of right sub-tree of  9: 0
  Sum of right sub-tree of  8: 9
  Node 8 replaced with  6 + 9 
  Sum of left sub-tree of  10: 15 <<<<Sum of left sub tree of 10
  Considering node 14
Considering node 12
Sum of left sub-tree of  12: 0
  Sum of right sub-tree of  12: 0
  Sum of left sub-tree of  14: 12
  Considering node 15
Sum of left sub-tree of  15: 0
  Sum of right sub-tree of  15: 0
  Sum of right sub-tree of  14: 15
  Node 14 replaced with  12 + 15 
 sum of right sub-tree of  10: 27  <<<sum of right sub tree of 10
  Node 10 replaced with  15 + 27 <<<<<Root replaced

Complexity analysis

All such kind of problems require to visit every node of the tree, hence complexity of all above problems is O(N).