## Double a Binary Tree

We take a binary tree and iterate from the root till the lowest sub tree. Each time we visit a node, we create a new node and duplicate the content. We add this node to the left child of the original node. This logic is recursive and execution goes to entire sub-trees level and completes the process. The resulting binary tree is also a binary tree with twice the height of the original.

## Source Code

``` 1  struct node * new_node(int val)
2  {
3    struct node * new_node = (struct node *)malloc(sizeof(struct node));
4    if(new_node) {
5      new_node->value = val;
6      new_node->left = 0;
7      new_node->right = 0;
8    } else {
9      exit(-1);
10    }
11    return new_node;
12  }
13
14  void double_tree(struct node* node) {
15    struct node* old_left;
16    if (node == NULL) {
17      return;
18    }
19    /* recurse to the subtrees */
20    double_tree (node->left);
21    double_tree (node->right);
22    /* duplicate this node to its left child */
23    old_left = node->left;
24    node->left = new_node(node->data);
25    node->left->left = old_left;
26  }```

You have viewed 1 page out of 248. Your C learning is 0.00% complete. Login to check your learning progress.

0

Similar topics related to this section