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

Linked list in C++

A linked list is a versatile data structure. In this structure, values are linked to one another with the help of addresses. I have written in an earlier post about how to create a linked list in C.  C++ has a library - standard template library which has list, stack, queue etc. data structures. But if you were to implement these data structures yourself in C++, how will you implement? If you just use new, delete, cout and cin, and then claim it is your c++ program, you are not conforming to OOPS concept. Remember you have to "keep it together". Keep all the functions and variables together - in a class. You have to have class called linked list in which there are methods - append, delete, display, insert, find, find_last. And there will also be a data - head. Defining node We need a structure for all these nodes. A struct can be used for this purpose, just like C. struct node { int val; struct node * next; }; Next we need to define our class. W
Post a Comment
Read more

Swap nodes of a linked list

Qn: Write a function to swap the adjacent nodes of a singly linked list.i.e. If the list has nodes as 1,2,3,4,5,6,7,8, after swapping, the list should be 2,1,4,3,6,5,8,7 Image from: https://tekmarathon.com Though the question looks simple enough, it is tricky because you don't just swap the pointers. You need to take care of links as well. So let us try to understand how to go about it. Take two adjacent nodes p1 and p2 Let prevnode be previous node of p1 Now link prevnode to p2 Link p2 to p1 Link p1 to next node of p2 So the code will be prevnode -> next = p2; p1 -> next = p2 -> next; p2 -> next = p1; But what about the start node or head? head node does not have previous node If we swap head with second node, modified head should be sent back to caller  To take care of swapping first and second nodes, we can write p1 = head; p2 = head -> next; p1 -> next = p2 -> next; p2 -> next = p1; head = p2;  Now we are read
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 (root -> v
Post a Comment
Read more