Archive for category Binary Tree

How to count number of nodes in a Binary Search Tree?


To count the number of nodes in a given binary search tree, the tree is required to be traversed recursively until a leaf node is encountered. When a leaf node is encountered, a count of 1 is returned to its previous activation (which is an activation for its parent), which takes the count returned from both the children’s activation, adds 1 to it, and returns this value to the activation of its parent. This way, when the activation for the root of the binary search tree returns, it returns the count of the total number of the nodes in the binary tree.

int count(struct tnode *p)
{
        if( p == NULL)
                return(0);
        else
                if( p->lchild == NULL && p->rchild == NULL)
                        return(1);
                else
                        return(1 + (count(p->lchild) + count(p->rchild)));
}

Try this on the binary search tree give below. Find out the number of nodes in the binary search tree using the program above.

Find out how do you get the height of the binary search tree?

Leave a comment

How to search in a Binary Search Tree?


An algorithm for searching a binary search tree follows immediately from the binary search tree property. Although the search algorithm can be cast in a recursive fashion, it’s just as easy (and more efficient) to write it iteratively. Here is a Search( ) function that shows how this is done:

Bnode *Search(Bnode *t, const TYPE &x)
// Returns pointer to a node matching the data x if
// such a node is in the tree t; otherwise, a 0 is returned
{
while (t) {
if (x == t->info) break;
t = (x < t->info) ? t->Left() : t->Right();
}
return t;
}

However, searching in binary search can be done in recursive fashion as well and hence most of the problems related to Binary Search Trees are done in recursive fashion, its worth looking into its recursive version as well:

/*
Given a binary tree, return true if a node
with the target data is found in the tree. Recurs
down the tree, chooses the left or right
branch by comparing the target to each node.
*/
static int search(struct node* node, int target) {
// 1. Base case == empty tree
// in that case, the target is not found so return false
if (node == NULL) {
return(false);
}
else {
// 2. see if found here
if (target == node->data) return(true);
else {
// 3. otherwise recur down the correct subtree
if (target < node->data) return(search(node->left, target));
else return(search(node->right, target));
}
}
}

Leave a comment

What is Binary Search Tree?


BINARY SEARCH TREE

This is a very special class of trees known as binary search trees. A binary search tree has binary nodes and the following additional property:

Given a node t, each node to the left is “smaller” than t, and each node to the right is “larger.” This definition applies recursively down the left and right subtrees. Figure 1 shows a binary search tree where characters are stored in the nodes.

Figure 1 also shows what happens if you do an inorder traversal of a binary search tree: you’ll get a list of the node contents in sorted order. In fact, that’s probably how the name inorder originated.

You may wonder what we mean by “smaller” and “larger” in our definition of binary search tree. This depends on the type of data being stored at the nodes. If, for instance, the data is integers, then the meaning of smaller and larger is obvious. More typically, though, the node data is some kind of structure, with one of the fields (called the key) used to make comparisons in a binary search tree.

Figure 1: Binary Search Tree

A quick video to have a better (visual) understanding of a Binary Search Tree.

3 Comments

What is a Binary Tree?


Go through my previous post about  What are Trees if you haven’t already read it to completely understand the binary trees.

Binary Trees

In general, tree nodes can have any number of children. In a binary tree, the nodes have no more than two children. Figure 1 has examples of binary trees. Figure 2 isn’t a binary tree because several of its nodes have three children. A node in a binary tree isn’t required to have two children. For example, node b in Figure 1  has only one child. Of course, the leaves of a binary tree have no children.

Figure 1: Binary Tree

Figure 2 : Not a Binary Tree

Every tree has a height, which is defined as the maximum number of nodes that must be visited on any path from the root to a leaf. For instance, the tree in Figure 1 has a height of 3. In turn, the depth of a node is the number of nodes along the path from the root to that node. For instance, node c in Figure 1  has a depth of 1. Also go through How to Find the height of a Binary Tree.

1 Comment

Binary Search Tree Traversal


Traversing binary search tree is very important as most of its objectives are accomplished by traversing in various ways. Most popular Binary Search Tree traversals are

  • Inorder Traversal of Binary Search Tree
  • Preorder Traversal of Binary Search Tree
  • Postorder Traversal of Binary Search Tree
  • Pre-order traversals : the root node is visited, then the child nodes (left to right).
  • In-order traversals: only makes sense in binary trees – the left node will be visited, then the root node, and then the right node.
  • Post-order traversals: the child nodes will be visited before the root node (left to right).


void inorder ( struct tnode *p){
if( p != NULL){
inorder(p->left);
printf("%d\t",p->data);
inorder(p->right);
}
}

void preorder ( struct tnode *p){
if( p != NULL){
printf("%d\t",p->data);
preorder(p->left);
preorder(p->right);
}
}

void postorder ( struct tnode *p){
if( p != NULL){
postorder(p->left);
postorder(p->right);
printf("%d\t",p->data);
}
}

2 Comments