# Archive for category Binary Tree

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

Posted by encrypt3d in Binary Tree, Data Structures on September 29, 2010

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?

### How to search in a Binary Search Tree?

Posted by encrypt3d in Binary Tree, Data Structures on September 25, 2010

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));

}

}

}

### What is Binary Search Tree?

Posted by encrypt3d in Basics, Binary Tree, Data Structures on September 25, 2010

**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.

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

### What is a Binary Tree?

Posted by encrypt3d in Basics, Binary Tree, Data Structures on September 25, 2010

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.

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.

### Binary Search Tree Traversal

Posted by encrypt3d in Binary Tree, Data Structures on September 21, 2010

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);

}

}