Given a Binary Search Tree that is populated with numerical data, write an algor
ID: 3833479 • Letter: G
Question
Given a Binary Search Tree that is populated with numerical data, write an algorithm that will determine the largest value in the tree that is less than the median of all the values in the tree.
Express your algorithm in Java-like pseudocode. You may use any of the operations supported by DJW's Binary Search Tree implementation (see BSTInterface.java).
Your solution must be developed at the application level.
Make sure you know what the median is.
If you use the operations in DJW's BSTInterface.java, please use numBST for the name of the BinarySearchTree object. Object instantiation and variable declarations are not needed. Do not include any logic in your solution that populates or changes the values in the tree.
Explanation / Answer
FindLargestValueSmallerThanMedian:
traverse numBST to ge count of nodes in Binary Search Tree
Traverse tree in inorder fashion, keeping two pointers, current and prev, where current points to current node and prev points to inorder successor of node.
Stop traversal when count of nodes is n/2 where n is number of nodes.
return prev.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.