Given a binary search tree and a \"target\" value, search the tree to see if it
ID: 3759322 • Letter: G
Question
Given a binary search tree and a "target" value, search the tree to see if it contains the target. The basic pattern of the lookup() code occurs in many recursive tree algorithms: deal with the base case where the tree is empty, deal with the current node, and then use recursion to deal with the subtrees. If the tree is a binary search tree, there is often some sort of less-than test on the node to decide if the recursion should go left or right. Write a pseudo code to implement the Lookup() algorithm.
Explanation / Answer
PSEUDO CODE : for Lookup()
search for key KEY in BinarySearchTree whose root is at node n:
if (KEY == n.KEY) {
return n.val
} else if (KEY < n.KEY and n has a left subtree) {
iteratively search for KEY in n's left part/ subtree
} else if (KEY > n.key and n has a right subtree) {
iteratively search for KEY in n's right part/ subtree
} else {
KEY not present in the BinarySearchTree
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.