C++ Programming: Program Design Including Data Structures 7th Edition 1. Find th
ID: 3868476 • Letter: C
Question
C++ Programming: Program Design Including Data Structures 7th Edition
1. Find the number of leaves in the binary tree with root A.
2. List the nodes of this binary tree in an inorder sequence.
3. List the nodes of this binary tree in a postorder sequence.
4. Suppose that you are given two sequences of elements corresponding to the inorder sequence and the preorder sequence. Prove that it is possible to reconstruct a unique binary tree.
5. Given the nodes of a binary tree in the preorder sequence and the postorder sequence, show that it may not be possible to reconstruct a unique binary tree.
Explanation / Answer
1. int findNumberOfLeafNodes(Node *a){
if (a->left == NULL && a->right == NULL)
return 1;
else if (a->left != NULL && a->right != NULL)
return findNumberOfLeafNodes(a->left) + findNumberOfLeafNodes(a->right);
else if (a->left == NULL && a->right != NULL)
return findNumberOfLeafNodes(a->right);
else if (a->left != NULL && a->right == NULL)
return findNumberOfLeafNodes(a->right);
}
The number of leaves in the given tree is 5
2. void inorder(Node *a){
if (a == NULL)
return;
inorder(a->left);
cout << a->data;
inorder(a->right);
}
Inorder Sequence is H K D B L I M E A R J C G
3. void postorder(Node *a){
if (a == NULL)
return;
postorder(a->left);
postorder(a->right);
cout << a->data;
}
Post order sequence is K H D L M I E B J F G C A
4.If the inorder and preorder sequence is given then we can reconstruct a unique binary search tree.Suppose for example we have two sequences:
Inorder sequence: D B E A F C
Preorder sequence: A B D E C F
In the case of preorder we know that left most node will be the root. So now A is root and we know that all the nodes in the left of A in order will make the left subtree and similarly the nodes to the left of A in inorder sequence will make the right sub tree. So if we recursively follow the same step we can construct a unique binarty search tree. for ex
A
D B E F C
A
B F
D E C
5.Given a Preorder and Postorder sequence we can not create a unique binary search tree. We can not establish any relation between the two sequences as we established in case 4 above. As in the absence of such a relation we can not create the unique binary search tree.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.