# Recursion and Binary Search Trees

Page 1 of 1

## 7 Replies - 3475 Views - Last Post: 10 August 2012 - 11:11 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=288440&amp;s=d06757ad161461ce2b6bf4b8f04a2998&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 MitulP91

Reputation: 1
• Posts: 64
• Joined: 18-July 12

# Recursion and Binary Search Trees

Posted 09 August 2012 - 02:04 PM

Hello everyone. Before I start off I'm aware of the rules where you are not meant to give me code. I'm not asking for code, but rather a step in the right direction. Just a point to start from.

I've been given an assignment to create a recursive algorithm that takes only a pointer r to the root of a binary tree and checks if the tree is a binary search tree. I don't actually need to make the tree, just this function.

The function call should look like this:

```bool check(Node * r);

```

and the included struct is:

```struct Node
{
int     key;
Node  * left;
Node  * right;
};

```

I simply don't know how to go about doing this. Any hints would be much appreciated.

Is This A Good Question/Topic? 0

## Replies To: Recursion and Binary Search Trees

### #2 MitulP91

Reputation: 1
• Posts: 64
• Joined: 18-July 12

## Re: Recursion and Binary Search Trees

Posted 09 August 2012 - 02:22 PM

This is what I managed to put together. Look right to anyone?

```bool check(Node * r)
{
if (r == NULL)
{
return true;
}

if ((r->left != NULL) && (r->right != NULL))
{
if ((r->key > r->left->key) && (r->key < r->right->key))
{
return true;
check(r->left);
check(r->right);
}
}
else
{
return false;
}
}

```

### #3 Skydiver

• Code herder

Reputation: 6071
• Posts: 20,894
• Joined: 05-May 12

## Re: Recursion and Binary Search Trees

Posted 09 August 2012 - 02:57 PM

Line 12 prevents line 13 and 14 from executing. You probably want to check the results returned by the children and make decision based whether both children are also binary search trees.

You are making the assumption that all lesser values go to the left, and all greater values go to the right. What if the tree maker wanted things the other direction?

Also, you are making the assumption that it is binary search tree only if every node has two children, or is a leaf. A binary search tree can be sparse, or lopsided.

You are on the right track, though of breaking the problem down to subtrees.

This post has been edited by Skydiver: 09 August 2012 - 02:56 PM

### #4 #define

• Duke of Err

Reputation: 1853
• Posts: 6,671
• Joined: 19-February 09

## Re: Recursion and Binary Search Trees

Posted 09 August 2012 - 02:58 PM

I think one branch can be null.

Binary search tree

### #5 baavgai

• Dreaming Coder

Reputation: 7119
• Posts: 14,841
• Joined: 16-October 07

## Re: Recursion and Binary Search Trees

Posted 10 August 2012 - 04:11 AM

Interesting. Your check for left and right should be independent.
```if (r->left!=NULL) {
if (r->key < r->left->key) { return false; }
//...
}

if (r->right!=NULL) {

```

I don't believe allowing for different tree directions is within the scope of your problem. It it were, you function sig would be different. Stick with the one you're using for now.

### #6 Skydiver

• Code herder

Reputation: 6071
• Posts: 20,894
• Joined: 05-May 12

## Re: Recursion and Binary Search Trees

Posted 10 August 2012 - 10:41 AM

Assuming that lesser values always go the left child is like assuming that everybody drives on the right side of the road, or everybody uses the metric system.

Edit: fixed typo.

This post has been edited by Skydiver: 10 August 2012 - 11:08 AM

### #7 baavgai

• Dreaming Coder

Reputation: 7119
• Posts: 14,841
• Joined: 16-October 07

## Re: Recursion and Binary Search Trees

Posted 10 August 2012 - 11:01 AM

Yeah, I'm an ugly American, sue me.

I agree, for a useful tree you'd really want a standard compare. Ideally you'd implement an operator override on less than somewhere. Or pass some compare interface. However, given the constraint of the function sig and the node type, you're limited. You could set up something global, but I really can't recommend that.

### #8 Skydiver

• Code herder

Reputation: 6071
• Posts: 20,894
• Joined: 05-May 12

## Re: Recursion and Binary Search Trees

Posted 10 August 2012 - 11:11 AM

He! He! He! :cheers:

I tried to be global and threw in the metric thing there for the rest of the world.

Yeah, having a global to switch directions just doesn't feel right.

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }