Is this valid? Why or why not?
Mathematically it's not a tree. However, it would be allowed in some programming languages as a valid representation of a tree.
The reason it is not mathematically a tree is that the node
a has two children,
b, which are the same. This is not allowed in a tree. If you have multiple children they must all be different.
In general, a tree is a set of nodes, where each node is either a leaf, or it has some children. If it has children, then the two children must all be distinct, and all their descendants must be distinct. Also, there must be some "root" node which all other nodes are descendants of. This does not qualify for this definition.
There is a difference between a tree and a representation of a tree. In a programming language, a mathematical tree is represented in a certain way. So for example, in your code it is represented with some
TreeNode objects which have a
left and a
Some programming languages would allow this code. It would represent the following tree:
Notice that this is a tree with three nodes, not two. That is why it is mathematically a tree: the two children in the above diagram are distinct. But they are represented in the same way, since they are both the same object
b, i.e. they are both the same
Just for fun: infinite trees
Here is a fun consequence of what you have done, in programming languages that allow it: infinite trees! Consider this code:
a = new TreeNode(1);
b = new TreeNode(2);
a.left = b;
a.right = b;
b.left = a;
b.right = a;
The result of this innocent-enough seeming sequence of statements is that we get the following monstrous infinite data structure:
/ \ / \
a a a a
/ \ / \ / \ / \
b b b b b b b b
... ... ... ... ... ... ... ...
This is a bit of a mess, so that is one reason programming languages might want to guarantee that all the nodes of a tree are represented distinctly, and so they might want to disallow the code that you wrote.