please find all solutions 10-CS501 Dt.pd ell Problem 1: Lookup) algorithm in bin
ID: 666342 • Letter: P
Question
please find all solutions 10-CS501 Dt.pd ell Problem 1: Lookup) algorithm in binary tree. Given a binary search tree and a "target" value, search the tree to see if it contains th get. The basic pattern of the lookup) code occurs in many recursive tree algorithms target. The basic pattern of the lookup) code occurs in many recursive tree agorithms 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. Problem 2: Insert o algorithm in binary tree node with the given Inserto - given a binary search tree and a nun number into the tree in the corect place. The inserto co h tree and a number, insert a new no the complication that it modifies the tree structure. As described a lling inserty with the num into the tree in the correct place. The inserto code is similar to lookup, hut with tructure. As described ahole, insert) returns hove, inserto ret 5 on this tree... the new tree pointer to use to its caller. Calling insert() with returns the treeExplanation / Answer
1)
2)
The base-case/recursion structure is similar to the structure in lookup() -- each call checks for the NULL case, looks at the node at hand, and then recurs down the left or right subtree if needed.
/*
Helper function that allocates a new node
with the given data and NULL left and right
pointers.
*/
struct node* NewNode(int data) {
struct node* node = new(struct node); // "new" is like "malloc"
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/*
Give a binary search tree and a number, inserts a new node
with the given number in the correct place in the tree.
Returns the new root pointer which the caller should
then use (the standard trick to avoid using reference
parameters).
*/
struct node* insert(struct node* node, int data) {
// 1. If the tree is empty, return a new, single node
if (node == NULL) {
return(newNode(data));
}
else {
// 2. Otherwise, recur down the tree
if (data <= node->data) node->left = insert(node->left, data);
else node->right = insert(node->right, data);
return(node); // return the (unchanged) node pointer
}
}
The shape of a binary tree depends very much on the order that the nodes are inserted. In particular, if the nodes are inserted in increasing order (1, 2, 3, 4), the tree nodes just grow to the right leading to a linked list shape where all the left pointers are NULL. A similar thing happens if the nodes are inserted in decreasing order (4, 3, 2, 1). The linked list shape defeats the lg(N) performance. We will not address that issue here, instead focusing on pointers and recursion.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.