2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ What is the definition of tree you are operating on? $\endgroup$ – greybeard Feb 25 at 18:09
  • $\begingroup$ Your code suggests you might be interested in trees as they are implemented in a programming language (rather than trees as a general mathematical data structure). For instance, the code you write would be allowed in some languages, and not allowed in others. $\endgroup$ – 6005 Feb 25 at 22:18
  • $\begingroup$ I assume by "tree" you mean "binary tree". One definition of binary tree is "a binary tree is either empty or a pair of binary trees called left and right". By that definition your data structure is a binary tree. Another is "a directed, labeled graph where all edges are labeled left or right, no node has two of the same kind of outgoing edge, the unique root node has no incoming edge, other nodes have one incoming edge, and there is a unique undirected path between any two nodes". By that definition your data structure is not a tree. So, what's your definition of "valid tree"? $\endgroup$ – Eric Lippert Feb 26 at 23:59
  • $\begingroup$ A tree is a connected acyclic graph. In your example you've made a cycle, so the graph is not a tree. $\endgroup$ – Brady Gilg Mar 3 at 21:15
7
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ You are assuming that the pseudocode in the OP corresponds to the set of two nodes, 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$ – 6005 Feb 25 at 21:57
  • $\begingroup$ Thanks. I don't know what binary trees are used for. I'm just doing the leetcode questions so I can pass my interview. $\endgroup$ – Garrett Feb 26 at 23:07
  • 2
    $\begingroup$ @Garrett: A good interviewer will dig into your toolbox to discover if your knowledge of basic data structures is deep or shallow. I would suggest to you that you learn what binary trees are used for, as they are foundational to the study of algorithms. $\endgroup$ – Eric Lippert Feb 26 at 23:50
4
$\begingroup$

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.

Short answer

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.

However...

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.

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
            /             \
         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.

$\endgroup$
  • $\begingroup$ Thank you. That helps. $\endgroup$ – Garrett Feb 26 at 23:08
  • $\begingroup$ @Garrett Glad to hear. $\endgroup$ – 6005 Feb 26 at 23:09
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.