(a) Consider the following Binary Search tree Write down the (i) in-order traver
ID: 3917221 • Letter: #
Question
(a) Consider the following Binary Search tree Write down the (i) in-order traversal 2 (ii) preorder traversal (ii) postorder traversal Do you notice an interesting property of the in-order traversal? What is it? (b) Let a binary search tree be defined by the following class public class IntTree ( private IntTreeNode overallRoot; // constructors and other methods omitted for clarity private class IntTreeNode f public int data; public IntTreeNode left; public IntTreeNode right // constructors omitted for clarity In class, we saw how to search for an element in a binary search tree. This question will demonstrate that binary search trees are more powerful. Describe an algorithm that calculates the k'th smallest element in the tree. (k, the input, is a number in 1,2,.. , n], where n is the number of nodes in the tree). You may find it helpful to modify the definition of IntTreeNode in order to accomplish this. Your algorithm should run in O(h) time, where h is the height of the tree. An O(n) solution will be given partial credit.Explanation / Answer
(i) In-order
Left - Root - Right
a b c d e f g h i
(ii) Pre-Order
Root - Left - Right
f c b a e d h g i
(iii) Post-Order
Left - Right - Root
a b d e c g i h f
Interesting thing about In-order traversal of Binary Search Tree is that it gives the sorted order
Note: One question at a time please -- Policy of Chegg
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.