Can the same node appear twice in a tree?
I'm asking about the node object itself, not the node's value. For example, in the following code, a's left and right are the same node, b.
a = new TreeNode(1);
b = new TreeNode(2);
a.left = b;
a.right = b;
Is this valid? Why or why not?
A tree is defined to be a set of nodes, with a parent-child relationship that satisfies certain properties. Thus, it doesn't make sense to ask whether a node can "appear" twice.
In your code snippet, you have constructed a DAG, not a tree.
a and b, with two edges. Another valid interpretation would be that it corresponds to a tree with three nodes, where the root is labeled with object a and the two leaves are labeled with object b.
$\endgroup$
Commented
Feb 25, 2020 at 21:57
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 and 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 right field.
Some programming languages would allow this code. It would represent the following tree:
a
/ \
b b
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 TreeNode object.
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
/ \
b b
/ \ / \
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.
A (rooted) tree is a structure composed of a set of nodes (note: set has no "repeats", by definition), one of which is the root of the tree, and the others are arranged as trees, whose roots are children of the root. Note that we have a direction (from root to children, down to leaves --nodes with no children). There is exactly one path from the root to any node.
A somewhat related structure is a DAG (directed acyclic graph), where you have nodes connected by edges with a direction (one-way streets, in other words). Again,nodes are unique, but in a DAG several edges can end at the same node. What distinguishes a DAG is that there are no cycles, sequences of edges that start at a node and lead back to it.
Then there are directed graphs, nodes connected by directed edges, but no other restrictions.
What comes naturally in a program is to have nodes (structures in memory) that reference others (thus directed edges, this node references that one). The result isn't always a tree, not even a DAG.
