Creating a Binary Tree

Let s create a binary tree by first defining a structure. Call the structure Metadata because it describes data that is used in the binary tree, and metadata refers to data that describes other data, such as how an employee ID can be used to get the employees name. Metadata typically refers to name /value pairs, or in our case, key/value pairs.

Each instance of the data structure is a node on the binary tree and contains four data elements. The first two data elements are the key and the value . In this example, both the key and value are char arrays. The size of these arrays is determined by the #define preprocessing directive at the top of this example. You set the array size by using the preprocessing directive because you can easily change its value in one place within the application without having to locate every place in the code where the array sizes are used.

The other two data elements of the metadata structure are pointers called left and right . Each of these points to a metadata structure. In other words, they point to the next node on the left and on the right of the current node. This enables the application to do two things. First, the application can move to the next level of the tree. It can also access both the key and the value of nodes at the next level.

You might become confused when looking at the example of the structure definition because the structure uses itself to initialize data elements of the structure. Here s what s happening. A key and related value are passed to the metadata structure when an instance of the metadata structure is declared, that is, when a new node is inserted into the binary tree. Both of these are passed as char pointers because they are arrays.

The application copies the key and the value to the data elements of the instance of the metadata structure by using the strcpy () function. The strcpy() function copies the second parameter to the first parameter. Notice the this operator is used in this example. As you ll recall from your programming course, the this operator tells the compiler that you want to refer to the data element of this instance of the structure instead of the parameter that was passed in.

The last two data elements to be initialized are the left and right pointers. Both of these are set to NULL because the new node doesn t have a child node when the new node is created. Later in this chapter, you ll define a function that adds a child node and replaces the NULL with reference to an actual node.

 #include <string.h> #define SIZE_KEY 32 #define SIZE_VALUE 256 typedef struct Metadata {  struct Metadata(char* key, char* value)  {  strcpy(this->key, key);  strcpy(this->value, value);  left = NULL;  right = NULL;  }  char key[SIZE_KEY];  char value[SIZE_VALUE];  struct Metadata* left;  struct Metadata* right; } METADATA; 

In addition to defining a structure, you ll also define the BinarySearchTree class. The BinarySearchTree class defines data members and member functions that create and manipulate a node. As illustrated in the code that follows , the class definition is organized into two areas, the private access specifier and the public access specifier. As you ll recall from your object-oriented programming class, the application can only access data and member functions defined within the public access specifier ; members defined within the private access specifier area of the class definition can only be accessed by member functions of the class. The private access specifier section of the BinarySearchTree class defines two data members, size and root . The size is an integer that stores the number of nodes on the tree. The root is a pointer to an instance of the metadata structure. In other words, root is the first node on the tree.

The private access specifier also contains nine member functions:

 addNode()  getNode()  removeAllNodes()  processNodesInOrder()  getTreeDepth()  containsNode()  removeNode()  removeRootNode()  moveLeftMostNode() 

These functions are used by functions defined in the public access specifier of the class definition to manipulate nodes on the tree. You ll learn how each of these functions works later in this chapter.

The public access specifier contains the constructor and destructor for the class and several member functions that enable the application to create and remove nodes and manipulate nodes on the tree. Here is a list of those member functions. You ll learn how they work later in this chapter.

 BinarySearchTree();  ~BinarySearchTree()  add()  remove()  removeAll()  get()  contains()  displayInOrder()  getSize()  getDepth() class BinarySearchTree {  private:  int size;  METADATA* root;  bool addNode(METADATA** current_node, METADATA* new_node);  bool getNode(METADATA* current_node, char* key, char* value);  void removeAllNodes(METADATA* node);  void processNodesInOrder(METADATA* node);  int getTreeDepth(METADATA* node);  bool containsNode(METADATA* node, char* key);  bool removeNode(METADATA** node, char* key);  void removeRootNode(METADATA** node);  void moveLeftMostNode(METADATA** node, METADATA* root);  public:  BinarySearchTree();  virtual ~BinarySearchTree();  bool add(char* key, char* value);  bool remove(char* key);  void removeAll();  bool get(char* key, char* value);  bool contains(char* key);  void displayInOrder();  int getSize();  int getDepth(); }; 

Constructor and Destructor

The constructor of the BinarySearchTree class initializes the root data member of the BinarySearchTree class with a NULL value. As you ll recall from the previous section, root is a pointer to an instance of the metadata structure and points to the root node for the binary search tree once a node is added to the tree.

The constructor also initializes the size data member to zero. This means there are no nodes on the tree. The size data member is incremented each time a new node is inserted into the tree and decremented when a node is removed from the tree. You ll see how these steps are done later in this chapter.

The destructor removes all the nodes from the tree and releases memory used by those nodes. The destructor doesn t directly remove the nodes. Instead, it calls the removeAll() member function that actually handles deleting nodes and releasing memory.

The following are definitions of the constructor and the destructor for the BinarySearchTree class:

 BinarySearchTree() {  root = NULL;  size = 0; }  ~BinarySearchTree() {  removeAll(); } 

add() and addNode()

You add a new node to the tree by calling the add() member function of the BinarySearchTree class as shown in the next code snippet. The add() function requires two arguments, a pointer to the key of the new node and another pointer to the node s value. In this example, we call these key and value.

Before the node is added to the tree, the add() function validates both the key and the value with two tests. First, it makes sure that the key and the value don t have a NULL value. Next, it tests to be sure that neither the key nor the value is larger than the array size allocated for the key. It does so by comparing the length of the key and the length of the value to the corresponding value defined in the #define preprocessor directive. If any of these tests fail, then the add() function returns a Boolean false to the statement in the application that calls the add() function.

If the key and value are valid, then the add() function proceeds to create the new node. First, it declares an instance of the metadata structure and passes the key and value to the instance. Previously in this chapter you learned that the key and value become the initial values for corresponding data elements in the metadata structure.

The final step in the process of adding a new node to the tree is to call the addNode() function. The addNode() function is defined within the private access specifier in the BinarySearchTree class and is responsible for placing the new node into the tree.

 bool add(char* key, char* value) {  if(key == NULL  value == NULL  strlen(key) > SIZE_KEY-1   strlen(value) > SIZE_VALUE-1)  {  return false;  }  METADATA* new_node = new METADATA(key, value);  return addNode(&root, new_node); } 

The addNode() function shown in the next code requires two arguments. The first argument is a pointer to a pointer that points to the current node. The other argument is a pointer to the new node. The process of adding a new node to the tree begins by the addNode() function determining if the new node passed to is NULL. When the value of current_node is NULL, then you ve reached a leaf node on the tree. This is where the addition takes place. All nodes are added as leaf nodes. If this is the first node being added to the tree, then the leaf node also happens to be the root node. The new node is assigned to the pointer field of current_node , and the size data member is incremented. This adds the new node to the tree. The addNode() function then returns a Boolean true , indicating that the operation is successful. You need to pass a pointer to a pointer as the first argument because you re going to alter the data in that node. What you re really passing is the address of the pointer field in the parent node. By passing the address of the pointer, you can change the pointer value in the parent. The pointer in the parent is changed to point to this new child node that s being added.

If the current node isn t NULL, the next step is to find where in the tree the node is to be added. This process is tricky because the new node must be located in a position where it will be either less than or greater than its parent node.

Here s how it works. The addNode() function compares the key of the current node to the key of the new node using the strcmp() function. If the return value of the strcmp() function is less than zero, then the key of the new node is less than the key of the current node. Then addNode() is called again recursively, but this time reference to the left node of the current node is passed as the first argument to the addNode() function. As you ll recall, the first argument is considered by the addNode() function as the current node. In this case, the left node of the current node is considered the current node. The second argument is the new node. Notice that the addNode() function is recursively called until the addNode() function finds a place for the new node. The first call to addNode() passes the first argument as the root node of the tree. Each subsequent call passes a root node of a subtree . Remember that each node in the tree can be considered a root node for all the nodes below it. The same rules apply at every node ”all the nodes on the left are less than and all the nodes on the right are greater than.

If the key of the new node is greater than the key of the current node, then a similar process occurs except the current node s right node is used instead of the left node when addNode() is subsequently called.

This recursive process continues until the first argument to addNode() points to NULL, which indicates a leaf node where the addition takes place.

If the key of the new node equals an existing node, then the new node is deleted and the addNode() function returns a Boolean false . This is because all keys must be unique: duplicate keys are not permitted on the tree.

 bool addNode(METADATA** current_node, METADATA* new_node) {  if(*current_node == NULL)  {  *current_node = new_node;  size++;  return true;  }   else  {  if(strcmp(new_node->key, (*current_node)->key) < 0)  {  return addNode(&((*current_node)->left), new_node);  }  else if(strcmp(new_node->key, (*current_node)->key) > 0)  {  return addNode(&((*current_node)->right), new_node);  }  else  {  delete new_node;  return false;  }  } } 

remove(), removeNode(), and removeRootNode()

Removing a node from the tree is a multiple-step process that begins when the application calls the remove() member function as shown in the next code snippet The remove() function requires the key of the node being removed. It then calls the removeNode() member function. The removeNode() function is a private member of the BinarySearchTree class and therefore cannot be called directly by the application.

The removeNode() function requires two parameters. The first is a reference to the current node being evaluated, which is where the search begins. You begin the search by passing the root node of the tree, then subsequent calls will pass the root of a subtree. You always have to think about the tree as being a set of subtrees ”each node is a root for all the nodes below it. The second parameter is the key received by the remove() function.

 bool remove(char* key) {  return removeNode(&root, key); } 

The removeNode() function shown in the next code snippet uses the value passed by the remove() function to locate the node that is being deleted. Before the search begins, the removeNode() determines if a root node passed to it by the remove() function is NULL. This may be the root node of the tree if this is the first call to the function, or it may be the root of a subtree. If it s NULL, then the Boolean value false is returned because the node to remove was not found.

If the root node isn t NULL, the search continues. The objective of the removeNode() function is to find a key of a node in the tree that matches the key passed by the remove() function. Once found, reference to the node that contains the key is passed to the removeRootNode() , which actually removes the node from the tree. The removeRootNode() may be removing the root node of the tree or a root of a subtree.

The search begins by comparing the key of the root node passed by the remove() function to the key passed by the remove() function. If the keys match, then the root node is passed to the removeRootNode() function where the node is removed. The size data member is decremented to reflect that a node has been removed from the tree. A Boolean true is then returned by the removeNode() function.

If there isn t a match, then the removeNode() function determines if the key of the root node is less than the key passed by the remove() function. If so, then the removeNode() function compares the key of the left node to that of the key passed by the remove() function. The removeNode() function is called recursively until a match is found, at which time the removeRootNode() function is called and passed the reference to the matching node.

If the key is greater than the key of the root node, then the key of the right node of the root node is compared to the key. Again, the removeNode() function is called recursively until there is a match, at which time the removeRootNode() function is called and passed a reference to the matching node.

 bool removeNode(METADATA** node, char* key) {  if(*node != NULL)  {  if (strcmp(key, (*node)->key) == 0)  {  removeRootNode(node);  size--;  return true;  }  else if(strcmp(key, (*node)->key) < 0)  {  return removeNode(&((*node)->left), key);  }  else  {  return removeNode(&((*node)->right), key);  }  }  else  {  return false;  } } 

The removeRootNode() member function is the function that actually removes a node from the tree. The term root node can sometimes be confusing because you intuitively assume that the root node is the first node on the tree. In reality, any node can be a root node for all the nodes below it in the tree. Even if the node is a leaf node, it s still a root node of the subtree. It just so happens that this subtree contains only one node. Therefore, we use the term root node in the name of this function.

The removeRootNode() function requires one argument, which is a pointer to a pointer for the node being removed. The removal process begins by declaring a pointer to the metadata structure. We call this pointer temp in the code example shown next.

Before removing the node, the removeRootNode() function determines if the node has a right child and left child node. If both the left and right child nodes are NULL, then no children exist and the delete operator is called to release the memory associated with this node. Then the pointer field in the parent node is set to NULL because this child node was removed. Note that if this were the only node in the tree, this call would set the root node of the tree to NULL, which makes sense because the tree would be empty.

If one child isn t NULL, then the right child is compared to NULL. This would be the case if the node being deleted doesn t have a right child. In this case, you change the pointer field in the parent to the node on the left of the one being deleted. The root node is assigned to the temp pointer to remember the location of the node that is being removed from the tree. Next, reference to the left node is assigned to the parent node. The delete operator then removes the node referenced by the temp pointer to release the memory associated with the node being deleted.

If the right node isn t NULL, then the removeRootNode() determines if the left node is NULL. This follows similar logic to the previous example, except the node being deleted doesn t have a left child, so the pointer in the parent node is set to the node on the right of the one being deleted. The reference to the root node is assigned to the temp pointer. Reference to the right node is then assigned to the parent node. The delete operator then releases the memory associated with the node being removed.

The last ”and most complex ”scenario is if the node being removed has both a left child and right child node. In this case, the removeRootNode() calls the moveLeftMostNode() function and passes it the address of the right node.

 void removeRootNode(METADATA** root) {  METADATA* temp;  if((*root)->left == NULL && (*root)->right == NULL)  {  delete(*root);  *root = NULL;  }  else if((*root)->right == NULL)  {  temp = *root;  *root = (*root)->left;  delete(temp);  }  else if((*root)->left == NULL)  {  temp = *root;  *root = (*root)->right;  delete(temp);  }  else  {  moveLeftMostNode(&((*root)->right), *root);  } } 

The objective of the moveLeftMostNode() function is to find the node that will replace the current root node of the subtree. To achieve this goal, you must move once to the right and then go down the tree as far left as possible until you find the smallest node on the right. The move to the right occurs when the moveLeftMostNode() is called the first time. You then move left subsequent calls to the function. Once the smallest value on the right is found, the node containing the smallest value becomes the new root node.

Let s see how this works by walking through the following definition of the moveLeftMostNode() function. This function requires two arguments, the current node being evaluated and the node that will be replaced . Remember, this function will copy the key and value from the smallest node on the right subtree to the node that s being removed. This replaces the node that s being removed with one of the leaf nodes, and then the leaf node is deleted.

If reference to the node being moved is not NULL and the left pointer of the node being moved is NULL, then you ve found the node that will be moved up to the position of the one that s to be removed. A pointer is declared and assigned to the node being moved. Next, the key and the value of the node are copied to the key and value of the root node. The root node in this case is the node that s being removed from the tree. Because you re moving the leftmost child of the right subtree, this leftmost child may have nodes to the right of it. The pointer value in the parent of the node that is being moved is set to the right pointer in the one that s being moved. This keeps these subnodes intact. Finally, the delete operator removes the node.

If you haven t found the leftmost node of the right subtree, then moveLeftMostNode() is called again. This time, the left child node is passed as the node to be moved to the root position. The root position is the node that is being removed.

 void moveLeftMostNode(METADATA** node, METADATA* root) {  if(*node != NULL && (*node)->left == NULL)  {  METADATA* temp = *node;  strcpy(root->key, (*node)->key);  strcpy(root->value, (*node)->value);  *node = (*node)->right;  delete(temp);  }  else  {  moveLeftMostNode(&((*node)->left), root);  } } 

removeAll() and removeAllNodes()

The previous section showed you several functions that remove one node from the tree. There are occasions when you ll need to clear the entire tree of nodes. To do this, you ll need to call the removeAll() function.

The removeAll() function is shown in the next code snippet and performs two operations. First, it calls the removeAllNodes() function, which is defined in the private access specifier section of the BinarySearchTree class. This is the function that actually removes all the nodes from the tree. The second operation is to reset the root and size data members of the BinarySearchTree class. The root data member is set to NULL, indicating there aren t any nodes on the tree. The size data member is set to zero, indicating that the tree is empty. The removeAll() function is also called by the destructor.

 void removeAll() {  removeAllNodes(root);  root = NULL;  size = 0; } 

The removeAllNodes() function, shown next, requires one argument, which is a reference to the root node. As long as the root node isn t NULL, the removeAllNodes() function calls itself each time, passing it first the left child node and then the right child node as the root node. The ordering of these calls is important. Remember that the root node is either the root node of the tree or the root of a subtree. You must remove all the child nodes before removing the parent. You recurse the left tree, recurse the right tree, then, when it returns to the caller, it s safe to delete the current node (root node) because all the children have been deleted. As with all recursive functions, you have to define a stopping point. In this case, if you are at a leaf node, the left and right pointers would be NULL and the calls to removeAllNodes() would return (they would not continue the recursion) because the node would be NULL.

A message is displayed on the screen stating the key and the value of the node that is being removed from the tree. The delete operator is then used to remove the node.

 void removeAllNodes(METADATA* node) {  if(node != NULL)  {  removeAllNodes(node->left);  removeAllNodes(node->right);  cout << "Removing node - key: " << node->key << "\t"  << node->value << endl;  delete node;  } } 

get() and getNode()

The get() member function of the BinarySearchTree class is called within the application whenever you want to retrieve the value of a node. To retrieve a value, you must provide the get() function with the search key and with the variable that will store the value once the key is found.

Here s how this works. As illustrated in the next code snippet, you pass the get() function two arguments. The first argument is a reference to the search key. In this example, the key is a string. Therefore, you pass the get() function a pointer to a char , which you ll recall from your programming class actually points to the first character of the string. The second argument is also a char pointer. This points to the first element of a character array that the get() function uses to store the value of the node that is associated with the search key.

Let s say that the search key is student ID 1234 and the value associated with the key is Bob Smith. You pass the get() function 1234 and the get() function copies Bob Smith to the value char array if the search key 1234 is found in a node of the tree. You then use the value char array throughout your application.

The get() function is defined in the public access specifier section of the BinarySearchTree class and is therefore accessible to an application. However, the get() function simply calls the getNode() member function, which is defined in the private access specifier section of the class. The getNode() function returns a Boolean true if the search key is found; otherwise , a Boolean false is returned. The return value also becomes the return value of the get() function.

 bool get(char* key, char* value) {  return getNode(root, key, value); } 

The getNode() function is where all the action occurs. Here the search is conducted and the value of the node is copied to the value array. As illustrated next, the getNode() function requires three arguments. The first argument is a reference to the root node. The root node is the starting point of the search and is usually the uppermost node of the tree, but it can be any node. The second argument is a reference to the search key, which is a char pointer in this example. The third argument is a reference to the variable that stores the value of the node that contains the search key. Both the search key and the value variable are the same as those passed to the get() function.

The getNode() begins processing by validating the root node. If the root node is NULL, then the value argument is set to an empty string (it sets the first character to NULL) and a Boolean false is returned by the getNode() function to indicate that the key was not found in the tree.

If the root node isn t NULL, then the search continues. The getNode() function is called recursively. Each time it is called, it compares the search key with the key of the root node. If they match, then the value of the root node is copied to the value variable and a Boolean true is returned by the function.

If the search key doesn t match the key of the root node, then the getNode() function determines if the search key is less than or greater than the key of the root node. Depending on the results of this comparison, the getNode() function calls itself and uses either the left child or the right child of the root node as the root node argument of the getNode() function. This process continues until either the search key matches the key of the root node or the root node is NULL, indicating the key doesn t exist in the tree. This type of search is where the power of binary trees comes into play. Notice that each time the function is called, by doing one comparison on the key, you eliminate half the remaining nodes from the search, so you re able to find the key very quickly even in a large data set.

 bool getNode(METADATA* node, char* key, char* value) {  if(node == NULL)  {  value[0] = ' 
 bool getNode(METADATA* node, char* key, char* value) { if(node == NULL) { value[0] = '\0'; return false; } else { if(strcmp(key, node->key) == 0) { strcpy(value, node->value); return true; } else if(strcmp(key, node->key) < 0) { return getNode(node->left, key, value); } else { return getNode(node->right, key, value); } } } 
 ';  return false;  }  else  {  if(strcmp(key, node->key) == 0)  {  strcpy(value, node->value);  return true;  }  else if(strcmp(key, node->key) < 0)  {  return getNode(node->left, key, value);  }  else  {  return getNode(node->right, key, value);  }   } } 

contains() and containsNode()

Previously in this chapter, you learned that a key in a tree must be unique. You cannot have two keys with the same key value. Don t confuse key value with the value stored in a node. A key value is the value of the key itself.

Before adding a new node to the tree, you should determine if the key of the new node already exists in the tree. It is possible to construct a binary tree that allows duplicate keys, but this is not a common implementation and goes beyond the scope of this chapter. In this case, you ve defined a rule for the tree that states all the keys must be unique.

You determine if the key already exists in the tree by calling the contains() member function of the BinarySearchTree class, which is illustrated next. The contains() function requires one argument, a reference to the key. It returns a Boolean true if the key exists; otherwise, a Boolean false is returned.

You ll notice that the contains() function is a simple function in that it has one statement. This statement calls the containsNode() member function. The containsNode() function searches the tree for the key and returns a Boolean true if the key is found; otherwise, a Boolean false is returned, which is then used as the return value of the contains() function.

The contains() function is defined in the public access specifier section of the BinarySearchTree class. The containsNode() function is defined in the private access specifier section of the same class.

 bool contains(char* key) {  return containsNode(root, key); } 

The containsNode() member function, as shown next, requires two arguments. The first argument is a reference to the root node. Any node can be the root node, but typically the first node of the tree is the root node because you want the search for the key to begin at the top of the tree. The second argument is reference to the key, which is the same key that is passed to the contains() function.

The process begins by determining if the root pointer is NULL. If the pointer is NULL, then the key doesn t exist and a Boolean false is returned; otherwise, the key is compared and the search continues.

First, the containsNode() function compares the key to the key of the root node. If there is a match, then a Boolean true is returned and the search ends. If they are different, then the containsNode() determines if the key is less than the key of the root node. If so, then the containsNode() calls itself and uses the left child node of the root node as the new root node.

If the key isn t less than the key of the root node, then the containsNode() determines if the key is greater than the key of the root node. If so, then the containsNode() calls itself using the right child node of the root node as the new root node.

The containsNode() is called recursively until either the key is found or until the value of the root node is NULL, indicating that you ve reached the end of the tree without finding the key.

 bool containsNode(METADATA* node, char* key) {  if(node == NULL)  {  return false;  }  else  {  if(strcmp(key, node->key) == 0)  {  return true;  }  else if(strcmp(key, node->key) < 0)  {  return containsNode(node->left, key);  }  else  {  return containsNode(node->right, key);  }  } } 

displayInOrder() and processNodesInOrder()

You can display the contents of the tree by calling the displayInOrder() member function of the BinarySearchTree class. As the name implies, the displayInOrder() function is a public function that displays the key and the value of all the left nodes followed by all the right nodes for each node in the tree.

As shown next, the displayInOrder() function has one statement that calls the processNodesInOrder() member function of the BinarySearchTree class. The processNodesInOrder() function is defined in the private access specifier section of the class and is therefore unavailable to the application.

You must pass the processNodesInOrder() function one argument, which is a reference to the root node. The root node is typically the first node of the tree, but you can start displaying the contents of the tree from any node by passing it as the argument to the processNodesInOrder() function.

 void displayInOrder() {  processNodesInOrder(root); } 

The definition of the processNodesInOrder() member function is illustrated next. You ll notice that this is a recursive function and is called multiple times in order to print nodes contained on the left and right branches of the tree.

Processing begins by determining if the root node is NULL. If so, you re at the end of tree. If it is not NULL, then the processNodesInOrder() is called again and passed the left child of the root node. The key and value of the node is then displayed on the screen.

This continues until keys and values of all the left nodes appear on the screen. A similar process is followed to display the right children of the root node. For any given node, all the left nodes will be printed first, then the node itself is printed, then all the right nodes.

 void processNodesInOrder(METADATA* node) {  if(node != NULL)  {  processNodesInOrder(node->left);  cout << "key: " << node->key << "\tvalue: " << node->value << endl;  processNodesInOrder(node->right);  } } 

getSize(), getDepth(), and getTreeDepth()

Previously in this chapter, you learned that a tree is measured by its number of nodes and levels. The number of nodes in a tree is called the size of the tree, and the number of levels is the depth of the tree. We ve defined member functions that you can use to determine the size and the depth of a tree.

The first of these functions is called the getSize() member function, which is shown next. This function simply returns the value of the size data member of the BinarySearchTree class. Functions that add and remove nodes adjust the value of the size data member so the size data member always reflects the current number of nodes in a tree.

 int getSize() {  return size; } 

The getDepth() member function determines the number of levels in the tree. This function calls the getTreeDepth() member function and passes it reference to the root node that is used as the starting level when calculating the depth of the tree. It returns an integer that represents the number of levels of the tree.

The getDepth() function and the getSize() function are both defined in the public access specifier section of the BinarySearchTree class. The getTreeDepth() function is defined in the private access specifier.

 int getDepth() {  return getTreeDepth(root); } 

The getTreeDepth() function is shown next and performs all the calculations to determine the total number of levels in a tree. The getTreeDepth() function requires one argument, which is a reference to the root node. This should be the first node in the tree, although you can use any node. If you do use a node other than the top node, the function calculates levels from that node to the end of the tree. Levels previous to this node are not considered in the calculation.

The process starts by determining if the tree is empty. If so, then the root node is NULL and a zero is returned. If the root node isn t NULL, then the getTreeDepth() function drills down each level of the tree by recursively calling itself. You get a NULL parameter when you reach a leaf node. This doesn t mean the tree is empty, it just means you reached a leaf node. Then the recursive calls return, incrementing the count value through each recursion to add up the levels.

Each time the getTreeDepth() function is called, the left child node and the right child node are passed to the getTreeDepth() function and the function returns an integer representing the level, which is assigned to either the depth_left variable or the depth_right variable.

The depth_left and the depth_right variables are compared. If the value of the depth_left variable is greater than the depth_right variable, the depth_left variable is incremented and returned by the getTreeDepth() function; otherwise, the depth_right variable is incremented and returned.

 int getTreeDepth(METADATA* node) {  int depth_left;  int depth_right;  if(node == NULL)  {  return 0;  }  else   {  depth_left = getTreeDepth(node->left);  depth_right = getTreeDepth(node->right);  if(depth_left > depth_right)  {  return depth_left + 1;  }  else  {  return depth_right + 1;  }  } }