Skip to main content

Binary tree functions

In this post we will write some functions for a binary search tree.

Find minimum of a binary search tree:

This function is quite simple. In a binary search tree, every node has values smaller than itself on left sub tree and values larger than itself on right subtree. So as we move to left, values get smaller and smaller.

Which means that the left extreme node is our minimum value. So if you keep traversing to left until you reach NULL, the last node is tree minimum.

int tree_minimum(NODEPTR nd)
{
   while(nd->left !=NULL)
       nd = nd->left;
   return nd->val;
}


Count the total number of nodes in a binary search tree:


This one needs a recursive function.

Total number of nodes in a binary tree = total number of nodes in its left subtree + 1 + total number of nodes in right subtree

And there is no recursion if node is NULL and the call must return 0.

And here is the function.


int count_nodes(NODEPTR nd)
{
   if(nd==NULL)
     return 0;
   else
     return  count_nodes(nd->left)+1+count_nodes(nd->right);
}

Search for a node in a BST

Let us discuss non-recursive searching of a value.

Binary search tree is an ordered tree. So when we compare search value with key of current node, if search value is greater than node value, we should branch to right. But if search value is smaller, we should branch to left. We should continue this process until value is found or a NULL is encountered.

  1. Start from root
  2. If key value of node matches search value return
  3. If key value of node is greater than search value, set node = node->left
  4. If key value of node is smaller than search value, set node = node->right
  5. Repeat steps 2 to 4 until match is found or node is NULL


NODEPTR search_node(NODEPTR root, int num)
{
   NODEPTR temp = root;
   while(temp!=NULL)
   {
      if(temp->val>num)
         temp = temp->left;
      else if(temp->val<num)
         temp = temp->right;
      else//we found a match
         return temp;
   }
   return NULL;//no match
}

Finally let us look at a function to count the number of leaf nodes.

Count the number of leaf nodes

This function would be similar to count function. But here we increment count only if node has left child as NULL and right child as NULL.


int count_leaf_nodes(NODEPTR nd)
{
    if(nd==NULL)
       return 0;
    else if(nd->left ==NULL  && nd->right==NULL)
       return 1;
    else 
       return count_leaf_nodes(nd->left)+count_leaf_nodes(nd->right);
}


Labels:

Comments

Post a Comment

Popular posts from this blog

Delete a node from doubly linked list

Deletion operation in DLL is simpler when compared to SLL. Because we don't have to go in search of previous node of to-be-deleted node.  Here is how you delete a node Link previous node of node of to-be-deleted to next node. Link next node of node of to-be-deleted to previous node. Free the memory of node of to-be-deleted Simple, isn't it. The code can go like this. prevnode = delnode->prev; nextnode = delnode->next; prevnode->next = nextnode; nextnode->prev = prevnode; free(delnode); And that is it. The node delnode is deleted. But we should always consider boundary conditions. What happens if we are trying to delete the first node or last node? If first node is to be deleted, its previous node is NULL. Hence step 3 should not be used.  And also, once head is deleted, nextnode becomes head . Similarly if last node is to be deleted, nextnode is NULL. Hence step 4 is as strict NO NO. And we should set prevnode to tail. After we put these things together, we have...
Post a Comment
Read more

Binary tree deletion - non-recursive

In the previous post we have seen how to delete a node of a binary search tree using recursion. Today we will see how to delete a node of BST using a non-recursive function. Let us revisit the 3 scenarios here Deleting a node with no children just link the parent to NULL Deleting a node with one child link the parent to  non-null child of node to be deleted Deleting a node with both children select the successor of node to be deleted copy successor's value into this node delete the successor In order to start, we need a function to search for a node in binary search tree. Did you know that searching in  a BST is very fast, and is of the order O(logn). To search Start with root Repeat until value is found or node is NULL If the search value is greater than node branch to right If the search value is lesser than node branch to left.  Here is the function NODEPTR find_node (NODEPTR root,NODEPTR * parent, int delval) { NODEPTR nd = root; NODEPTR pa = root; if (ro...
Post a Comment
Read more

Function to sort an array using bubble sort

Quick and dirty way of sorting an array is bubble sort. It is very easy to write and follow. But please keep in mind that it is not at all effecient. #include<iostream> using std::cin; using std::cout; void readArray(int arr[],int sz); void printArray(int arr[],int sz); void sortArray(int arr[],int sz); void swap(int &a,int &b); int main() {    int sz;    cout<<"Size of the array=";    cin>>sz;    int arr[sz];    readArray(arr,sz);     sortArray(arr,sz);   cout<<"Sorted array is ";   printArray(arr,sz); } void readArray(int arr[],int sz) {  for(int i=0;i<sz;i++)    {       cout<<"arr["<<i<<"]=";       cin>>arr[i];   } } void printArray(int arr[],int sz) {  for(int i=0;i<sz;i++)    {       cout<<"arr["<<i<<"]=";    ...
Post a Comment
Read more