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.

Double a Binary Tree

Source Code

struct node * new_node(int val)
{
  struct node * new_node = (struct node *)malloc(sizeof(struct node));
  if(new_node) {
    new_node->value = val;
    new_node->left = 0;
    new_node->right = 0;
  } else {
    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.

 Vote 0

Similar topics related to this section

Tree and Binary tree, Binary tree, traverse Binary tree, Binary search tree, double Binary tree, mirror Binary tree, height of Binary tree, heap, Complexity,

# C Programming Language (Prentice Hall Software)
# Let Us C Paperback - 2006 by Yashavant Kanetkar
# Understanding and Using C Pointers Core techniques for memory management
# Data Structures Using C and C++ Paperback - 1998
# Data Structures In C Paperback - August 11, 2008 by Noel Kalicharan