What Makes a Tree a Tree
Trees can come in many shapes and sizes. There are, however some constraints to making a valid tree.
- A tree has a single root
- A child has exactly one parent
- A tree is fully connected (IE a single tree)
- A tree has no cycles (IE no loops)
Any combination of the following represents a valid tree:
Below are some examples of invalid trees.
A cycle Again, cycles are essentially loops that occur in our tree. In this example, we see that our leaf has two parents. One way to determine whether your data structure has a cycle is if there is more than one way to get from the root to any node.
Two Trees This example would be considered two trees, not a tree with two parts. In this figure, we have two fully connected components. Since they are not connected to each other, this is not a single tree.