Problem 95 - To Tree, or not to Tree -

[Peter]

Hello

I would expect that

[1 [2 [3 [4 false nil] nil] nil] nil]

would validate as a binary tree, but the problem seems to indicate it
differently

(= (__ [1 [2 [3 [4 false nil] nil] nil] nil])
false)

Why is this not a valid binary tree?

Tx

Peter

[Peter]

Ah...never mind. I was misinterpreting the meaning of nil in the value

Apologies for the noise

Peter

[chepprey]

No worries. I hope the "noise" actually starts picking up around here
again now that the holidays are over.

[David]

I'm also confused why that wouldn't be a binary tree, anyone mind
clarifying?

Thanks,
David

[Damien Lepage]

The problem states that "Each node in the tree must have a value, a left child, and a right child."

So my understanding is that "false" is not a valid node because it is just a value, the 2 children are missing.

On the other side, "nil" doesn't represent an empty value, but means "no node", so it's fine as a left or right child.

2012/3/3 David <pick...@gmail.com>

--
Damien Lepage
http://damienlepage.com

@damienlepage

linkedin.com/in/damienlepage

[David]

Ah ok that makes more sense and my solution passes all the tests now.
Thanks.

On Mar 3, 4:52 pm, Damien Lepage <damienlep...@gmail.com> wrote:
> The problem states that "Each node in the tree must have a value, a left
> child, and a right child."
> So my understanding is that "false" is not a valid node because it is just
> a value, the 2 children are missing.
> On the other side, "nil" doesn't represent an empty value, but means "no
> node", so it's fine as a left or right child.
>

> 2012/3/3 David <pickda...@gmail.com>

> @damienlepage <https://twitter.com/#!/damienlepage>
> linkedin.com/in/damienlepage <http://www.linkedin.com/in/damienlepage>

[JorgeD]

Sorry for disturbing 5 years later, but... false is "just a value" but 1, 2, 3 and 4 are only just values and yet they are nodes (i.e., kind of roots of a subtree).

Why is false not a node?

Thanks in advance!

[Leif]

Hi, Jorge.

To expand upon Damien's answer:

The difference is that 1, 2, 3, and 4 are at the "value" position.  The structure of these trees is either:
[value left-node right-node] (node with value)
nil (empty node)

These are the only structures that are valid nodes.

So, in [4 false nil], 4 is correct because it is in the value position, and doesn't have to be a tree, nil is correct because it is in the right-node position, and it represents an empty node.  "false," however, is incorrect because it is in the left-node position, but it is a value, not a node.  To make it a node, you would need to write [false nil nil].

HTH,
Leif

[JorgeD]

Hi Leif,

thanks a lot - and please excuse me for the delay.

Now I see the problem: it was not about "false" being a value or not but it was all about the *position*!

Best regards,

Jorge