4. In C++: Construct a full BST of height 3 containing all numbers from 1 to 15 via an iterated insertion done by FCS function insert of slide 13 of week 5 (make a C++ adaptation of the FCS C code of Figure 5.35). Modify FCS function lookup of slide 12 of week 5 so that it returns the depth of the found element, in case the element is in the set represented as a BST, and ?1 in case the element is not in the set (make a C++ adaptation of the FCS C code of Figure 5.34). Run your modified lookup function on the tree you constructed by iterated insertion and demonstrate that your tree has height 3.

Figure 5.35

#include #define TRUE 1 #define FALSE 0 typedef int BOOLEAN; typedef int ETYPE; typedef struct NODE *TREE; struct NODE { ETYPE element; TREE leftChild, rightChild; }; TREE insert(ETYPE x, TREE T) { if (T == NULL) { T = (TREE) malloc(sizeof(struct NODE)); T->element = x; T->leftChild = NULL; T->rightChild = NULL; } else if (x element) T->leftChild = insert(x, T->leftChild); else if (x > T->element) T->rightChild = insert(x, T->rightChild); return T; }

figure 5.34

#include #define TRUE 1 #define FALSE 0 typedef int BOOLEAN; typedef int ETYPE; typedef struct NODE *TREE; struct NODE { ETYPE element; TREE leftChild, rightChild; }; BOOLEAN lookup(ETYPE x, TREE T) { if (T == NULL) return FALSE; else if (x == T->element) return TRUE; else if (x element) return lookup(x, T->leftChild); else /* x must be > T->element */ return lookup(x, T->rightChild); }

FCS: Binary Search Trees BOOLEAN lookup (ETYPE x, TREE T) (1) if (T== NULL) (3) else if(x==T->element) (5) else if (x T->element/ Fig. 5.34. Function lookup (x, T) returns TRUE if r is in T, FALSE otherwise