Question

Make the following assumptions: Assume a binary search tree holds integer numbers Write a pseudocode for a binary tree search algorithm that searches in the tree (starting at root) for a node which meets the following requirements, and prints a message when found:

(a) has a value that is one third as large as either its left or right child node. Think carefully about what steps are needed to do the search, and review the insert and search methods for BST

Answer 1

pseudocode for binary search tree

struct node* search(struct node* root, int key)

{

    if (root == NULL || root->key == key)

       return root;

    if (root->key < key)

       return search(root->right, key);

return search(root->left, key);

}

Insert Method In binary Search Tree

struct node* insert(struct node* node, int key)

{

    if (node == NULL)

return newNode(key);

  if (key < node->key)

        node->left = insert(node->left, key);

    else if (key > node->key)

        node->right = insert(node->right, key);   

    return node;

}

Search Method In binary Search tree

struct node* search(struct node* root, int key)

{

    if (root == NULL || root->key == key)

       return root;

    if (root->key < key)

       return search(root->right, key);

    return search(root->left, key);

}