How to double a binary tree?

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);
  }
  return new_node;
}

void double_tree(struct node* node) { 
  struct node* old_left; 
  if (node == NULL) {
    return;
  }
  /* 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 252. Your C learning is 0.00% complete. Login to check your learning progress.

‹ # ›

Questions index C Questions C++ Questions Win32 MFC COM/DCOM DLL Questions