Trees and Searching

A data structure is a method to organize the information in a manner such that we can process that information efficiently. The data structure has two categories:

· Linear Data Structure

· Non-Linear Structure

A tree is a non-linear data structure. It is used to represent data items which are having a hierarchical relationship between them. A logical representation of the tree is given below. A tree grows from top to bottom. A tree consists of root and nodes. A tree is a same sort of data structure like a linked list and the one distinction is that in a linked list every node can just link to another node but in a tree, every node can connect to numerous nodes.

Let us see some terminologies related to the tree.

· Root

It is the topmost element in the tree. It does not contain any parent node. In the above tree, ‘A’ is the root node.

· Nodes

Elements of a tree are nodes. They store some information. They contain a link to another node. Nodes can be numbers, strings or characters. In the following tree, nodes are A, B, C, D, E, F AND G.

· Parent Node

It is the immediate predecessor of any node. In the above tree, the parent node for node G is A.

· Child Node

It is the immediate successor of any node. Nodes B and F are children or child nodes of A.

· Leaf Node

It is the node that has no child. Node E, C, G and D are leaf nodes.

· Non-Leaf Node

It contains at least one child node. All the other nodes except leaf nodes are non-leaf nodes. A B and F are non-leaf nodes in the above tree.

· Path

It is a sequence of successive edges from the origin node to the target node.

· Ancestor

It is any forerunner node on the route from the root to that node.

· Descendant Node

It is any descendant node on the route from that node to a leaf node.

· Sibling

It is all the children of the same parent. Node E and C sibling because they same parent B. Similarly, G and D are siblings having the same parent F.

· Degree

It is simply the total number of children of a node. The degree of node A is 2 because it has two child nodes. While the degree of leaf nodes is zero.

· Depth of Node

It represents the number of edges from the root to the desired node. The depth of node C in the above tree is 2 because it contains two edges from the root to node C.

· Height of Node

It represents the number of edges in the lengthiest path from that node to the leaf node.

· Level of Node

It is the number of edges from the root to that node in a given path. In the above tree, the level of node E is 2 because it contains 2 edges in its path from root node A.

Level of a tree = Height of a tree.

Level of a node ≠ Height of a node.

Types of Tree

It has the following different types:

· General Tree

It stores the element in hierarchical order in which the top-level element is always present at level zero as a root element. All the nodes except the root node are present at several levels.

To understand this, let us consider a tree in which the root node is A while its child nodes are B, C and D. Child nodes of C are E, F and G. Nodes B, C and D constitute the siblings because they are present at the same level. Similarly, nodes E, F and G are siblings. Node A contains three subtrees named T1, T2 and T3. This tree is also known as a ternary tree because it contains three subtrees.

· Forest Tree

It is a collection of separate trees that can be achieved by removing the root node and edge which connecting the root node of the first-level node.

Let’s consider the above tree in which the root node is A. We will delete the edge joining the root node A to first level nodes B, C and D. Node C, E, F and G has one forest node named as ‘F1’. In the same way, node B and D forest paths ‘F2’ and ‘F3’.

· Binary Tree

It is a data structure in which every node does not have greater than two child nodes. Every node has left and right child nodes. The number of children a node can have range from 0, 1 or 2.

Let us consider a tree in which root node A has atmost two children that are B and C. Node B has two children D and E. While node C has two children F and G.

· Binary Search Tree

It fulfills a certain ordering characteristic. In a binary search tree, the values of each node in the left child will be smaller than the root while the elements present in the right subtree are larger than or equal to the root node elements.

Let’s consider a tree in which the root node is 10 having two child nodes 6 and 12. While node 6 has further two child nodes 3 and 7. And node 12 has root nodes 11 and 13. Now if we want to search 11 in this tree, firstly 11 will be compared with 10. As searching element 11 is larger than 10, so we will move towards the right subtree. Now searching element 11 is less than root node 12, so we will go to the left child of root node 12. Hence 11 can be found quickly and the searching process is fast.

· Expression Tree

It is a specific kind of binary tree that is used to represent an expression. The expression can be composed of constants, variables and operators which are arranged in a specific format. It is a special kind of tree in which leaves or external nodes act as operands. And all the operators store in internal nodes.

Let’s consider an infix expression and we want to represent it in form of a tree. Firstly, we have to check the left and right side of this expression.

(a + b*c) +(d / h)

As we know that while solving mathematical expression, high precedence is of power. Then multiplication and division have high precedence. On looking at expression, the b*c term will be solved first and then the d/h term according to the rules of precedence. Then we will take the + operator in the root and ‘a’ on the left side. And we will connect b*c with + operator on the right side. Now we will take the second + operator in the root node and attach (d/h) on its right side and (a+b*c) on the left side.

Implementation of Trees

There are mainly two ways to implement tree data structure:

· Linked List

· Array

· Linked List

In this method, every element is placed in a node. Every node has two pointers i.e left and right pointer. The left pointer is pointing to the left child of the tree. And the right pointer is pointing to the right child of the tree. When there are no more children, the pointers will have a null value.

· Array

In this method, we take an array of some particular size. Then we traverse the array level by level. In array, first, we write a root node and its child. The root is stored at index 0. If the parent is at some index ‘x’,

Left Child = 2x + 1

Right Child = 2x + 2

If we have a child node at some index ‘c’ , then parent node will be

Parent Node = ⌈c/2⌉-1

Tree Traversal

In tree traversal, we need to go to every one of the node of a tree. The order in which we visit its nodes will differ based on the method we choose to traverse this tree. There are three paths to any tree:

· Root

· Left subtree

· Right subtree

Let’s consider a tree in which the root is ‘a’, left subtree consists of ‘b’, ’d’, ’e’ and right subtree consists of ‘c’ and ‘f’.

The above tree can be traversed by following three ways:

· Pre-Order Traversal

In this, when we traverse a tree, the order that we must follow is going to be:

First, go to the root, then go to all elements of the left subtree. Then we visit all elements of the right subtree of the root.

Root — Left Tree — Right Tree

For the above tree, firstly we will go to root node ‘a’. Later we visit the left subtree rooted at node ‘b’. As node b has further left and right subtree, so same pre-order traversal procedure will be followed. Now we move onto the right subtree of node ‘a’. As ‘a’ is rooted at subtree ‘c’, so we will give the root first. Later we move to the left sub-tree ‘f’. For the left tree rooted at ‘f’, we will give the root first. Then we go to the right tree and no element is there. Then subtree rooted at ‘f’ will be completely traversed. The right of the ‘c’ node contains no element. So we can say that subtree rooted at ‘c’ has been completely traversed.

a b d e c f

· In-Order Traversal

In this, first, we traverse the left subtree, then traverse the root and then traverse the right subtree.

Left Tree — Root — Right Tree

Let’s consider the above tree in which we have root node ‘a’, left subtree and right subtree. Now left subtree will be traversed first. In the left subtree, we have root node ‘b’ and we will traverse its left subtree firstly. Left sub-tree of node ‘b’ is ‘d’ which does not have any element. Then we will go to the right subtree ‘e’ which does not contain any element. So, now subtree rooted at ‘d’ has been completely traversed. Now we will go to the right subtree of root node ‘a’. In the right subtree, we must move to the left subtree. In this manner, left subtree rooted at ‘f’ will be completely traversed. There are no elements in the right tree of ‘c’.

d b e a f c

· Post-Order Traversal

In this, we look at the left subtree first, then the right subtree and only then we will give the root.

Left Tree — Right Tree — Root

Now again consider the above tree, in which the root node is ‘a’. Its left subtree is ‘b’,’d’,’e’ and right subtree is ‘c’,’f’. Node ‘b’ contains left subtree ‘d’ and right subtree ‘e’. So we will traverse the left subtree ‘d’ first. Left subtree ‘d’ is null then we will go to the right tree. Right tree ‘e’ is also null. So left tree rooted at ‘d’ has been traversed. Then we will move towards the right subtree of B which is the tree rooted at E. Right subtree ‘e’ is null. Now subtree rooted at ‘b’ has been completely traversed. Right now we will move onto the right subtree of ‘a’ which is ‘c’ and ‘f’. We will move towards the left subtree rooted at ‘f’. The left tree and right tree both are null. Now subtree ‘f’ has been completely traversed. The right side subtree of ‘c’ is empty therefore we will go to the root. Now subtree rooted at ‘c’ has been completely traversed.

d e b f c a

Searching

It is a method of locating an item inside the list of items that are stored in any sequence. Suppose we have a list of elements as follows and we need to find 6 in this list. Firstly, 6 will be compared with 2.As 6 is not equal to 2, so it will be compared with 5.Again 6 is not equal to 3 so it will be compared with the next element. Now element 6 will be found and the searching process will be completed.

Linear Search

In this searching technique, we compare the elements of the array one by one with the element that we are searching for. Let us consider we have an array as follows. It contains a total of 8 elements. Suppose we want to search 42 elements in the array. There will be two types of cases. Either element will be present or not. If the element is present, then we want to print the location of that element where that element exists in this array. If the element does not exist then we want that our program should print the element not found.

We will start searching from index zero. And then we will gain access to every element of the array and to determine whether our desired data is present or not. If data is present then that location otherwise we will move to the next element. There will be two cases to stop this searching process. The first stopping condition is that we found that element. If data is not present in the array, we have reached the end of the array and we have to stop.

Now let’s have a look at the program of linear search. We use a for loop in which the index value starts from zero and go up to index value 7.

Binary Search

In this searching technique, initially, we have to sort out an array and then apply binary search. This method takes less time as in comparison to the linear search. The array should be in sorted order to apply binary search.

Let’s take a sorted array as shown below.

And we want to search for 59 in this array. Firstly we will find the mid position of this from where we can divide this array into two halves. So, we will have two variables at the leftmost and rightmost position of this array as L and R.

Mid = ⌊(L+R)/2⌋

= ⌊(0+9)/2⌋ = 4

So, mid value is 4.There can be occur three types of case such as:

Case 1 : Data = = x[Mid]

Case 2 : Data < x[Mid]

Case 3 : Data > x[Mid]

Here , we have case 3 in which data value 59 is greater than mid element 25.So our desired data is present to the right side on mid element.

As of now, we are considering the right side of this array so the left element will move towards the right.

Mid = ⌊(5+9)/2⌋ = 7

Now desired data element 59 is less than mid element 63. Now left element will remain in the same position but the right element will move towards the left from the mid element by one position.

Mid = ⌊(5+6)/2⌋ = 5

Data element 59 is greater than mid element 45. So the left element will move one position from the mid element. Now left and right element will point towards the same element. Now finally we have found 59 and it will return the index of 59.

Mid = ⌊(6+6)/2⌋ = 6

Now let’s take a look at the program of the binary search algorithm.