Trees: data structure

Trees concept

Trees represent one of the most important types of data structures in computing. They can be implemented in virtually any programming language.

The structure of a tree defines an arrangement of hierarchically arranged elements. The image below illustrates the representation of a tree, where you can see the analogy of the term used for the structure.

It is very useful in many real-world applications, such as directory structures in an operating system, graphical interfaces, databases and websites. See below two examples.

A tree shaping relationships in a social network

A tree modeling the folder structure in an operating system

Structure of a tree

Every tree is made up of two basic elements called:

• nodes.
• edges, that interconnect these nodes.

See the illustration in the image below.

Tree nodes represent spaces where various types of information can be stored, such as a telephone, a date, a name, a mailing list, a profile of a user on a social network, to name a few.

The edges represent relationships between these nodes. They represent the way nodes connect, and this relationship depends entirely on how the tree is used and the type of information the tree nodes store. For example:

• in a tree that shapes relationships in a social network, the edges can represent degrees of friendship.
• in a tree that shapes the folder structure of an operating system, edges can represent degrees of belonging (which folders belong to which other folders).

The big difference from a tree to other common data structures (such as arrays, lists, queues, and stacks) is that trees are not organized in a sequence. In a tree we cannot determine the next element and the previous element because its information is not organized in a queued manner.

See the illustration below for this difference.

In a list, each information is related to two other elements: the previous and the next

In a tree, each information (node) can be related to more than two elements

For this reason, trees are called nonlinear structures. And this makes it a very special structure with many different properties and characteristics.

Hierarchical Properties of a Tree

Root node

Every tree has one main node called root. The root represents the starting node of all tree types.

Child nodes and parents nodes

From the root, all lower nodes attached to a higher node are called child nodes. All higher nodes, which generate lower nodes, are called parent nodes.

Leaf node

Nodes that have no children are called leaf nodes.

The term “leaf node” alludes to the leaves of a tree, as they represent the end of the branch. The image below illustrates this metaphor.

Sibling nodes

Another important concept is the concept of brotherhood between nodes. Two nodes are siblings if they descend directly from the same parent node. See the examples in the illustrations below.

Degrees and order of a tree

“Degree” is the property that qualifies the nodes of a tree, it defines the number of children each node of a tree has. See the illustrations below.

“Order” is a concept that qualifies the entire tree. The order of a tree is defined by its highest degree node. Eg if the tree’s highest degree is 3, then the tree has order 3. See below for some illustrations.

Árvore de ordem 2

Árvore de ordem 3

Árvore de ordem 4

Ancestor and descendant

“Ancestor” is a concept that qualifies higher nodes than lower ones. When there is a set of edges that connect an upper node A to a lower node B, we say that A is ancestor of B.

“Descendant” is a concept that qualifies lower nodes in relation to higher nodes. When there is a set of edges that connect a lower node B to an upper node A, we say that B is descended from A.

Depth of a node

Depth is a concept that qualifies a node of a tree. It defines the distance from a given node to the root.

Level of a tree

The level defines the depth slices of a tree, so that the children of a node are always placed at later levels.

Height of a tree

Represents the largest depth of the tree. Represents the distance between the root and a leaf node of the highest level of the tree.

Subtree Concept

From the root, each new child represents a subtree, a new tree that recursively resets itself.

Computational representation

To computationally represent a tree, we need two structures: one to represent the tree nodes and one to represent the entire tree.

Representation of an order 2 tree (binary)

The code below presents a possible structural representation for a tree of order 2 (known as a binary tree). Note that in the node class (lines 7-18) we have two pointers (lines 9-10), one for the left child and one for the right child.

1./* Class that represents binary Tree*/
2.public class BinaryTree {
3.    Node root; // pointer to the root node
4.}
5.
6./* Class representing tree nodes*/
7.public class Node {
8.    int value; // value stored in node
9.    Node left; // pointer to the left child node
10.    Node right; // pointer to the right child node
11.    /* Node Constuctor*/
12.    Node(int value) {
13.        this.value = value;
14.        right = null;
15.        left = null;
16.    }
17.}

Representation of an order 4 tree (quadtree)

The code below presents a possible structural representation for a tree of order 4 (known as quadtree). Note that in the node class (lines 7-16) we have a pointer array (line 9) rather than two left and right pointers.

1./* Class that represents QuadTree*/
2.public class QuadTree {
3.    Node root; // pointer to the root node
4.}
5.
6./* Class representing tree nodes*/
7.public class Node {
8.    int value; // value stored in node
9.    Node[] children; // array of pointers to child nodes
10.    /* Node Constuctor*/
11.    Node(int value) {
12.        this.value = value;
13.        children = new Node[4]; // initialize the array of pointers
14.    }
15.}

The codes shown above represent only the structures of trees. In addition to structural representation, trees have several operations, such as the basic operations of: insertion, removal, search, among others.