Question

Answer the following question(s) concerning implementing recursive functions to perform operations on linked lists of nodes arranged as binary trees. For these questions, use the following struct definition for the nodes of the tree (we will not templatize the node here, so you do not have to write template functions for these questions, just assume trees of <int> values):

struct BinaryTreeNode
{  
  int item;
  BinaryTreeNode* left;
  BinaryTreeNode* right;
};

----------------------------------------------

Given a node for a Binary Tree and an (integer) item to search for, return true if the item is in the tree, and false otherwise. For this problem, the tree is not guaranteed to be arranged as a binary search tree, e.g. it is not necessarily the case that the item in the left child is smaller than a given nodes item nor that the right child is larger than the nodes item. So the nodes are still arranged as a binary tree, but they do not have the guaranteed ordering of the left and right children in relation to the parent nodes item.

So you need to search the whole tree, and return a boolean true if the item being searched for is in the tree, and false if the item is not in the tree. Your base case of course is a response of false if you are searching an empty node, otherwise you need to test your nodes item to see if you found what you are searching for, and if not, you then have to use recursion to check the left and right children.

The signature for the function you are to write is as follows:

/** search a Binary Tree 
 * Search given binary tree starting at the given node for the indicated
 * value.  The tree is not a Binary Search Tree, so we can assume that
 * left child values are less than the node value nor that right child
 * values are all greater than the node value.  This function returns
 * a boolean result of true if the search succeeds and we find the item,
 * and false if the item is not in the tree.
 *
 * @param node The node of the (sub)tree we are to begin searching from.
 * @param searchItem The (int valued) item we are to search for in the
 *   binary tree.
 *
 * @returns bool true if search is successful and searchItem is somewhere
 *   in the tree, false if the item is not in the tree./** search a Binary Tree 
 */
bool searchTree(BinaryTreeNode* node, int searchItem)
{
}

Answer 1

The completed code is given below-

bool searchTree(BinaryTreeNode* node, int searchItem)
{
   if(node == NULL)
       return false;
  
   if(node->item == searchItem)
       return true;
  
   if(searchTree(node->left, searchItem) == true)
       return true;
   else
       return searchTree(node->right, searchItem);
}