What are Trees?


A tree is a hierarchical collection of nodes. One of the nodes, known as the root, is at the top of the hierarchy. Each node can have at most one link coming into it. The node where the link originates is called the parent node. The root node has no parent. The links leaving a node (any number of links are allowed) point to child nodes. Trees are recursive structures. Each child node is itself the root of a subtree. At the bottom of the tree are leaf nodes, which have no children.

There is a directionality to the links of a tree. In the strictest definition of a tree, the links point down the tree, but never up. In addition, a tree cannot contain cycles. That is, no path originating from a node can return to that node.

Figure  1 shows a set of nodes that have the properties of trees. Figure 2 shows a set of nodes that do not constitute a tree. That’s because node d has two parents, and two cycles are present (abd and acd).

Figure 2: Difference between a tree and Not a tree

Trees represent a special case of more general structures known as graphs. In a graph, there are no restrictions on the number of links that can enter or leave a node, and cycles may be present in the graph.

A tree

This is very general definition of a tree, however, specific data structures like Binary Tree are mostly used in real applications in computer science. You would like to read What is a Binary Tree and How to find the height of the Binary Tree?

Advertisements
  1. What is a Binary Tree? « Encrypt3d
  2. Height of the binary tree! « Encrypt3d
  3. What is Binary Search Tree? « Encrypt3d

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: