How many degree1 vertices and degree2 vertices are there in

How many degree-1 vertices and degree-2 vertices are there in a full binary tree with 4 leave vertices_____ 2 degree-1 vertices and 2 degree-2 vertices 2 degree-1 vertices and 1 degree-2 vertices 0 degree-1 vertices and 3 degree-2 vertices 3 degree-1 vertices and 0 degree-2 vertices Cannot decide In a binary tree with height of h, how many leaves can this tree have at most?_____ 1 h 2^h 2^h + 1 None of the above What is the worst case running time to insert a vertices in a balanced binary search tree? O(1) O(log n) O(n) O(n log n). None of the above Tree Give a pointer-based representation (C++ declaration) for a tree with the root r. Except the constructor and its implementation, you do not need to include other methods.

Solution

1. C
   A full binary tree (sometimes a proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children, so the number of degree-1 vertices is zero. So in our question we have 4 leaf nodes in the last level(it means its height(h) is 2 (2^h=2^2=4)) rest of the nodes are root/intermediate nodes and their degree is 2, so total number of degree-2 vertices is 3 (total vertices = (2^(h+1)-1), ignore leaves(4). total = (2^(h+1)-1)-4 = (2^(2+1)-1)-4 = (7-4) = 3.

2. C
   In the question, it says atmost leaf nodes means maximum possible leaf nodes, in full binary search tree its possible to have maximum number of leaf nodes. As explained in above answer the number of leaf nodes in full binary search tree of height(h) is 2^h.

3. B
A balanced binary search tree is nothing but an AVL tree. When inserting an element into an AVL tree, you initially follow the same process as inserting into a Binary Search Tree. Once this has been completed, you verify that the tree maintains the AVL property. If it does not, then you perform tree rotations going upwards from the inserted node to rectify this. Here AVL property means the difference between heights of left and right subtree is not more than 1 for every node in a tree.

4.
#include<iostream>
using namespace std;
struct Tree {
   int val;
   Tree *left,*right;
   Tree() : left(NULL),right(NULL){}
   Tree(int v) :val(v),left(NULL),right(NULL){}
};
int main() {
   Tree *root=new Tree();
   Tree *temp=new Tree(2);
   root->left=NULL;
   root->right=temp;
   cout<<root->right->val;
}