1.Write a method using Java syntax that takes a reference ‘r’ to the root of a b

Question

1.Write a method using Java syntax that takes a reference ‘r’ to the root of a binary tree and returns the total number of leaves in the tree. You may use the Node class (structure) provided on the slides.   

[ The signature of the method is as follows:       int NumberOfLeaves(Node r) ]

2.Suppose an AVL tree the following items are inserted in the given order:

      29, 18, 11, 23, 38, 6, 16, 19, 17, 25, 26, 27

Show (draw) the construction of the tree at each insertion. If, at any insertion, the AVL property is violated then

      i) identify the node that violates the AVL property

      ii) indicate what type of rotation needed to restore the balance

      and iii) restore the balance (AVL property) of the tree before inserting the next item

Clearly indicate the final tree after all insertions.

3.Suppose, in a binary tree, tracing of a path from the root (1st node) to a leaf can be encoded by a binary string where 0 indicates “go to the left child” and 1 means “go to the right child”. Hence a string 1011 means “starting from root go to right (level 1), then go to its left child (level 2), then go to right child (level 3), and finally go to right (level 4), which is the desired leaf. Using this encoding scheme can you suggest an algorithm to reach the nth node in a complete binary tree? Indicate the running time of the algorithm.

4.Suppose the following integers are in index 1 to index 13 of an array in the given order:

5, 22, 19, 56, 50, 25, 1, 3, 10, 6, 32, 12, 11               

Construct a level-order tree with the items in the above order and then, using the heap methods, convert the level-order tree to a min-binary heap (draw the resulting min-heap).   

Explanation / Answer

#include #include /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node* left; struct node* right; }; /* Function to get the count of leaf nodes in a binary tree*/ unsigned int getLeafCount(struct node* node) { if(node == NULL) return 0; if(node->left == NULL && node->right==NULL) return 1; else return getLeafCount(node->left)+ getLeafCount(node->right); } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode(int data) { struct node* node = (struct node*) malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return(node); } /*Driver program to test above functions*/ int main() { /*create a tree*/ struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); /*get leaf count of the above created tree*/ printf("Leaf count of the tree is %d", getLeafCount(root)); getchar(); return 0; }

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---