Trees

Trees are non-linear data structures. They implement a hierarchical structure consisting of a set of nodes. Each node (a node is a member of the tree) except the root node will have only one parent but can have multiple children (called child nodes). The root node is the starting point of the tree – it does not have a parent node. The structural view of a tree should give you a good understanding about a tree.

In the above diagram ‘A’ is the root node. It has 3 child nodes- B, C and D. B has 2 child nodes E and F while C has only one child node G. As indicated above every node except the root node has a single parent node. No node in a tree can have two parent nodes.

Every node has a path connecting it to every other node. There are 2 links that have to be traversed if you want to reach ‘A’ from node ‘E’. Thus we say that the length of the path from E to A (or A to E) is 2. The length from B to E is 1.

The depth of a node is the length of the path of a node from the root node. This value is an indicator as to how far off the node is from the root. The depth of the root is 0. The height of the tree is the depth of the farthest node. In our case it would be 2 (A to E or A to F).

The degree of a node is equal to the number of its child nodes. B has a degree of 2.

Levels: Nodes B,C and D are at Level 1 while E and F are at Level 2 in the tree.

Subtree and supertree: A tree actually consists of many subtrees rooted together. In the above case node B, E and F form a subtree. This subtree is rooted at node B. Supertree is the parent of the subtree.

An example of a tree: Most Operating Systems organize their file structure in the form of a tree. We’ll have a drive, under which we have a set of directories and under each directory you can have sub-directories or files. Check out the Windows Explorer and you’ll discover the concept of trees and sub-trees.

Binary Trees

We’ll mainly focus on binary trees which are effective when searching. Searching through a large amount of data is generally time consuming when using other data structures. Binary trees facilitate searching. So, what is a binary tree? A tree in which every node has two children is a binary tree.

You can create a tree using nodes (just like we created a linked list). Every node of a tree will contain:

1. Value stored at the node
2. A pointer to the next node on the right
3. A pointer to the next node at the left

In our linked list we had a node called the ‘head’. This basically was a node that contained the starting location of the linked list (because we need to know from which memory location our data structure starts).

In a tree we will use the same concept to identify the starting point of the tree. This node will only contain a single pointer pointing to the first node (i.e. the root node) of the tree. This is also called a ‘tree pointer’.

In the above diagram we’ve illustrated a small and simple binary tree with a root node, 2 nodes branching off from the root and a tree pointer. All the ‘P’s in the figure denote a pointer (i.e. we’ll have to store memory locations). These memory locations will help us in identifying the two nodes to the left and right of the current node.

The figure below uses a few values to make the concept clear.

The reason binary trees are useful for searching is because we will insert nodes in an organized manner (i.e. we’ll insert them in a sorted fashion so locating an element becomes easy- it’s always easier to locate something in an arranged group than in an unsorted group). To achieve this, before inserting an element we’ll check as to whether the element has a value greater than the current node. If so then we need to place the element to the right of the current node, else to the left. Check out the diagram below (assume that we have created a binary tree to hold integers):

Check the left and right values at each node in the diagram. The right node will always have a value greater than the parent node while the left node will always have a value lower than its parent.

You can check out an application of binary trees here.