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 {
  return new_node;

void double_tree(struct node* node) { 
  struct node* old_left; 
  if (node == NULL) {
  /* recurse to the subtrees */
  double_tree (node->left); 
  double_tree (node->right); 
  /* duplicate this node to its left child */
  old_left = node->left; 
  node->left = new_node(node->data); 
  node->left->left = old_left; 

About our authors: Team EQA

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