You are given a binary tree that encodes a dynamic sequence of n elements. We wo

Question

You are given a binary tree that encodes a dynamic sequence of n elements. We would like to augment each node of the tree with a boolean field, named sameSubtree, that indicates true if the left and the right subtrees encode the same subsequence, false otherwise. In the figure below, a 1 indicates true, and 0 false. Note that the leaves are augmented with 1 since both their left and right subtrees are null, and that node 5 is also augmented with 1 since its left and right subtrees encode the same subsequence even though they are of different shapes. Given 17 10 the tree with no augmentations, please design and analyze an algorithm that can augment each node as described above. You may also augment each node with other information, for example, subtree sizes or heights, that may aid in augmenting sameSubtree.

Explanation / Answer

Implemented in C language.

below is my program.

// Code is working great for the height and size of tree
// For augmentation with boolean (1/0) it is not working perfectly because the subsequence word is not clear to me.
// So what I have considered in my code is that if the number of 1's in left side and right side of current node are same then assign it 1 else assign 0 value.

#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
    int val,aug,h,size;
    struct node *left,*right;
}node;

node* createnode(int x)
{
    node* temp = (node*)malloc(sizeof(node));
    if(temp)
    {
        temp->val = x;
        temp->aug = -1;
        temp->h =-1;
        temp->size = 1;
        temp->left = temp->right = NULL;
    }
    return temp;
}

void inorder(node *root)
{
    if(root)
    {
        inorder(root->left);
        printf("[%d(%d)],",root->val,root->aug);
        inorder(root->right);
    }
}
int Augmenttree(node** root)
{
    if(*root==NULL) return 0;
    if((*root)->left==NULL && (*root)->right==NULL)
    {
        (*root)->aug = 1;
        (*root)->h = 1 ;
        (*root)->size = 1;
        return 1;
    }
    int x = Augmenttree(&((*root)->left)); // x is sum of all 1's in left subtree;
    int y =Augmenttree(&((*root)->right)); // y is sum of all 1's in right subtree;
  
    // doing calculation for height and size of current root node
    if((*root)->left)
    {
            (*root)->size =(*root)->size + (*root)->left->size;
            (*root)->h = (*root)->left->h;
    }
    if((*root)->right)
    {
        (*root)->size = (*root)->size + (*root)->right->size;
      
        if((*root)->h<(*root)->right->h)
            (*root)->h = (*root)->right->h;        
    }
    // Finding augmentation value of current root node
    if(x==y)
    {
        (*root)->aug = 1;
      
        return x+y+1;  
    }
    else
    {
        (*root)->aug = 0;
      
        return x+y;
    }
}
int main()
{
    node *root =NULL;
    root = createnode(17);
    root->left = createnode(8);
    root->left->left = createnode(6);
    root->left->right = createnode(10);
    root->left->right->left = createnode(7);
    root->left->right->right = createnode(7);
    root->right = createnode(5);      
    root->right->left = createnode(2);
    root->right->left->left = createnode(3);
    root->right->left->right = createnode(3);
    root->right->left->right->right = createnode(1);
    root->right->right = createnode(2);
    root->right->right->left = createnode(3);
    root->right->right->right = createnode(1);
    root->right->right->right->left = createnode(3);
  
    //inorder(root);
  
    Augmenttree(&root);
    inorder(root);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.