Tuesday, 14 May 2013
Question:
Write a C++ program to.
1) Create a binary search tree named left tree and show the inorder, preorder and postorder traversal of that
left BST tree.
2) Similarly, create a binary search tree named right tree and show the inorder, preorder and postorder
traversal of that right BST tree.
3) After creating left and right binary search trees, one by one pick up a node value from right binary
Marks: 20
search tree by any traversing method and then insert that value (which you picked up from right tree node)
in left binary search tree. Discard any duplicate value (in both right and left binary search trees) during
insertion of a value from right binary search tree to left binary search tree.
4) The left binary search tree will be modified after inserting values from right binary search tree. Show the
inorder, preorder and postorder traversal of that modified left binary search tree.
Note:
Please watch the attached demo.wmv video for complete details of what is required from you in this 3
assignment. The diagram given below is showing the pictorial representation of left binary search tree , right
binary search tree and the modified left binary search tree which is developed after inserting values into left
binary search tree from right binary search tree.
Left Binary Search Tree:
15
11 22
24
10 12 20
19 23 25
Right Binary Search Tree:
10
155
64 14 20
19
23
rd
Modified left binary search tree:
15
4
11 22
10 12 20 24
25 23195
6
14
Solution Guidelines:
1. First understand the code given in handouts about binary search tree.
2. You can use code give handouts to complete desired task.
3. For clearly understanding of assignment task see demo.wmv file attached with assignment file.
4. If you have any ambiguity about assignment send your query at cs301@vu.edu.pk.
Lectures Covered: This assignment covers Lecture # 10 to 15
Deadline: Your assignment must be uploaded / submitted on / before, Wednesday May 15, 2013.
Write a C++ program to.
1) Create a binary search tree named left tree and show the inorder, preorder and postorder traversal of that
left BST tree.
2) Similarly, create a binary search tree named right tree and show the inorder, preorder and postorder
traversal of that right BST tree.
3) After creating left and right binary search trees, one by one pick up a node value from right binary
Marks: 20
search tree by any traversing method and then insert that value (which you picked up from right tree node)
in left binary search tree. Discard any duplicate value (in both right and left binary search trees) during
insertion of a value from right binary search tree to left binary search tree.
4) The left binary search tree will be modified after inserting values from right binary search tree. Show the
inorder, preorder and postorder traversal of that modified left binary search tree.
Note:
Please watch the attached demo.wmv video for complete details of what is required from you in this 3
assignment. The diagram given below is showing the pictorial representation of left binary search tree , right
binary search tree and the modified left binary search tree which is developed after inserting values into left
binary search tree from right binary search tree.
Left Binary Search Tree:
15
11 22
24
10 12 20
19 23 25
Right Binary Search Tree:
10
155
64 14 20
19
23
rd
Modified left binary search tree:
15
4
11 22
10 12 20 24
25 23195
6
14
Solution Guidelines:
1. First understand the code given in handouts about binary search tree.
2. You can use code give handouts to complete desired task.
3. For clearly understanding of assignment task see demo.wmv file attached with assignment file.
4. If you have any ambiguity about assignment send your query at cs301@vu.edu.pk.
Lectures Covered: This assignment covers Lecture # 10 to 15
Deadline: Your assignment must be uploaded / submitted on / before, Wednesday May 15, 2013.
Binary tree traversal: Preorder, Inorder, and PostorderIn order to illustrate few of the binary tree traversals, let us consider the below binary tree:
Preorder traversal: To traverse a binary tree in Preorder, following operations are carried-out (i) Visit the root, (ii) Traverse the left subtree, and (iii) Traverse the right subtree.
Therefore, the Preorder traversal of the above tree will outputs:
7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10Inorder traversal: To traverse a binary tree in Inorder, following operations are carried-out (i) Traverse the left most subtree starting at the left external node, (ii) Visit the root, and (iii) Traverse the right subtree starting at the left external node.
Therefore, the Inorder traversal of the above tree will outputs:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10Postorder traversal: To traverse a binary tree in Postorder, following operations are carried-out (i) Traverse all the left external nodes starting with the left most subtree which is then followed by bubble-up all the internal nodes, (ii) Traverse the right subtree starting at the left external node which is then followed by bubble-up all the internal nodes, and (iii) Visit the root.
Therefore, the Postorder traversal of the above tree will outputs:
0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7
Therefore, the Preorder traversal of the above tree will outputs:
7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10Inorder traversal: To traverse a binary tree in Inorder, following operations are carried-out (i) Traverse the left most subtree starting at the left external node, (ii) Visit the root, and (iii) Traverse the right subtree starting at the left external node.
Therefore, the Inorder traversal of the above tree will outputs:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10Postorder traversal: To traverse a binary tree in Postorder, following operations are carried-out (i) Traverse all the left external nodes starting with the left most subtree which is then followed by bubble-up all the internal nodes, (ii) Traverse the right subtree starting at the left external node which is then followed by bubble-up all the internal nodes, and (iii) Visit the root.
Therefore, the Postorder traversal of the above tree will outputs:
0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7
