# Binary search Tree:Help

Discussion in 'Java' started by brianm, Jan 10, 2005.

1. ### brianmGuest

Is this implementation of a binary search tree correct ?

numbers from 0 to 14 arranged in a binary tree (binary search tree). Is
this correct ? (left node is less, right node is greater than the
current node)

7
6 8
5 9 2 12
4 10 3 11 1 13 0 14

brianm, Jan 10, 2005

2. ### Guest

I'm not able to follow where the numbers lie in your tree, but there is
no one binary search tree of those numbers. You can make up different
trees based on when you insert numbers into the tree. But you have the
basic premise right. All elements to the right are larger than the
root. All elements to the left are smaller than the root.
You could also include equality with the root in one of them.

, Jan 10, 2005

3. ### Mike SchillingGuest

"brianm" <> wrote in message
news:...
> Is this implementation of a binary search tree correct ?
>
> numbers from 0 to 14 arranged in a binary tree (binary search tree). Is
> this correct ? (left node is less, right node is greater than the
> current node)
>
>
> 7
> 6 8
> 5 9 2 12
> 4 10 3 11 1 13 0 14

The formatting make this difficult to read, but if 7 is the root, 6 and 8
its children, and 9 the right child of 6, this is incorrect. Every member of
a node's left subtree needs to be less than every member of its right
subtree.

Mike Schilling, Jan 10, 2005
4. ### Lee WeinerGuest

In article <>, "brianm" <> wrote:
>Is this implementation of a binary search tree correct ?
>
>numbers from 0 to 14 arranged in a binary tree (binary search tree). Is
>this correct ? (left node is less, right node is greater than the
>current node)
>
>
>7
>6 8
>5 9 2 12
>4 10 3 11 1 13 0 14
>

Your diagram is a little hard to read, but if 7 is your root node, and 6 and 8
are the children off the root, then your diagram is not correct. For
starters, the nodes containing 0, 1 and 2 should all be children of the 6
node, not the 8 node. There are other mistakes.

Lee Weiner

Lee Weiner, Jan 10, 2005
5. ### brianmGuest

Here it is again...

7
6 8
5 9 2 12
4 10 3 11 1 13 0 14

brianm, Jan 10, 2005
6. ### Bjorn AbelliGuest

"brianm" wrote...
> Here it is again...

And it's still difficult to comprehend...

> 7
> 6 8
> 5 9 2 12
> 4 10 3 11 1 13 0 14

Binary tree roots doesn't have "middle nodes", only left and right nodes
("binary" means "two").

My guess is that you try to show that, and you just don't know how to
replace tabs with spaces?

So if we reformat your tree accordingly...

7
6 8
5 9 2 12
4 10 3 11 1 13 0 14

....we find several mistakes in the tree.

As Mike wrote, *every* node to the left, *including* subnodes, must be less
than the root.

To show a small example:

8
3 11
1 5 9 13

Look closely to the tree, and you see that *every* number on the right of
*any* other number in the tree is higher. If we *flatten* the tree, it would
look like:

1 3 5 8 9 11 13

I hope you see the logic. Note that an implementation of a binary tree in
many cases contains "empty" nodes, as it's difficult to predict how the
nodes to be inserted are distributed.

This is also a valid binary tree, though "unbalanced" (x stands for empty
nodes).

7
2 x
x 5

To implement a balanced tree "cost" more upon insertion, as it includes
moving already inserted nodes to new places. The tree above would after
balancing look like:

5
2 7

In *both* cases you can see it flattened like:

2 5 7

----------------------

public class Node
{
private Node left = null;
private Node right = null;
private int value;

Node(int i)
{
value = i;
}

{
if (i > value)
{
if (right == null) right = new Node(i);
}
else if (i < value)
{
if (left == null) left = new Node(i);
}
}

public int getValue() { return value; }
}

-------------------------

// Bjorn A

Bjorn Abelli, Jan 10, 2005