We are hiring content writers to work from home

Resources » Articles/Knowledge Sharing » Education

# Btree data structure

 Posted Date: 31-Aug-2009 Last Updated: 31-Aug-2009 Category: Education Author: SUMIT ROY Member Level: Bronze Points: 5

Programming & Data Structures - Final and Solutions- Dec 19, 2005
(I gave 5 points for each question, including 5 each for Questions 5a and 5b)
1. The post-order traversal of a binary search tree gives: 20 35 30 41 45 42 40 53 58 60 55 52.
Draw a diagram of the tree.
Ans.
52
40 55
42 60
30 53
35
20 45
41
58
2. If a complete binary tree is to be constructed with height 10, what is the minimum and
maximum # of leaves it can have? Count the root at height 0, the first two children at height 1,
etc.
This is a complete binary tree, not a search tree. So the leaf nodes are all at the last level. If
the tenth level is full, there will be 2^10 leaf nodes, which is the maximum # of nodes. The
minimum you can have is just one node (left-most) at the 10th level.
Max: 210=1024 Min: 1
3. Consider a set S={12, 3, 23, 11, 7, 8, 33, 4, 17}. Using the first element as pivot, write the
steps involved in running the Quicksort algorithm on the set. At each step, give the resulting
set.
Step 1 : 3 11 7 8 4 12 23 33 17
Step 2 : 3 7 8 4 11 12 17 23 33
Step 3 : 3 4 7 8 11 12 17 23 33
Step 4 : 3 4 7 8 11 12 17 23 33
Step 5 : 3 4 7 8 11 12 17 23 33
Step 6:
4. A text file "in.txt" contains lines of words separated by spaces. Write a C++ program to read in
the file, replace spaces by underscore, and write to another file "out.txt". A sample input and the
corresponding output are as follows:
in.txt out.txt
My Documents My_Documents
Program Files Program_Files
My unsaved school documents My_unsaved_school_documents
Ans.
#include
#include
#include
#include
using namespace std;
int main() {
ifstream IN;
ofstream OUT;
string s;
char c;
IN.open("in.txt");
OUT.open("out.txt");
while(!IN.eof()){
getline(IN,s);
for (int i=0;i c=s.at(i);
if (!isspace(c))
OUT< else
OUT<<'_';
}
OUT< }
IN.close();
OUT.close();
}
Almost all of you had a variation of the following program:
The problem with this program is that even the newline characters
#include
#include
are replaced by underscore so that "out.txt" ends up being a
#include
single line file. Please check it out. The isspace() function reports
using namespace std;
true all spaces, tabs as well as newline characters.
int main() {
ifstream IN;
ofstream OUT;
Despite this, I gave credit for those who wrote this answer.
string s;
char c;
IN.open("in.txt");
OUT.open("out.txt");
while(!IN.eof()){
IN.get(c);
if(isspace(c))
OUT.put('_');
else
OUT.put(c);
}
IN.close();
OUT.close();
}
5. Consider a Binary SearchTree
class BTree {
int key;
BTree* left;
BTree* right;
BTree* parent;
}
a)Write a member function int sum_of_keys(int m) that returns the sum of all key values in the
tree less than a given value m. Just give the function implementation, nothing else.
int BTree::sum_of_keys(int m){
int l=0, r=0;
if( (this->left==NULL) &&(this->right==NULL) ){
return ((this->key)>m) ? (this->key) : 0 ;
}
else
{ if( (this->key)>m)
if(this->left){ return this->key;
l=(this->left)->sum_of_keys(m); else
return 0;
}
if(this->right){
r=(this->right)->sum_of_keys(m);
}
return ((this->key) > m ) ? (this->key)+l+r : l+r ;
}
}
b) Write a non-member function int sum_of_leaves(BTree* root) that returns the sum of keys in
the leaf nodes of the tree with root given in the argument. Just give the function implementation,
nothing else.
int sum_of_leaves(BTree* root){
int l=0, r=0;
if ( (root->left == NULL) && (root->right == NULL) ){
return root->key;
}else{
if(root->left){
l=sum_of_leaves(root->left);
}
if(root->right){
r=sum_of_leaves(root->right);
}
}
return l+r;
}

Did you like this resource? Share it with your friends and show your love!

Responses to "Btree data structure"

No responses found. Be the first to respond...

Feedbacks

## Post Comment:

• Do not include your name, "with regards" etc in the comment. Write detailed comment, relevant to the topic.
• No HTML formatting and links to other web sites are allowed.
• This is a strictly moderated site. Absolutely no spam allowed.
•  Name: Sign In to fill automatically. Email: (Will not be published, but required to validate comment) Type the numbers and letters shown on the left.

 Next Resource: IT Previous Resource: Registration of B.A / B.Com. Degree Examinations in Kerala University Return to Resources Post New Resource Category: Education

Post resources and earn money!

More Resources
 Popular Tags Tag posting guidelines Search Tags

### Subscribe to Email

• Get Jobs by Email
• Forum posts by Email
• Articles by Email
• Awards & Gifts
Active Members
Today
Last 7 Days
more...