AVL Tree

  Consider the tree as shown below:

The above tree contains nodes with values as 14, 15, 4, 9, 7, 18, 3, 5, 16, 20, 17 respectively. The root node is 14. The right subtree contains the numbers greater than 14 and the left subtree contains the numbers smaller than 14. This is the property of the binary search tree that at any node, the left subtree contains the numbers smaller than this node and the right subtree contains the numbers greater than this node.

Now suppose that we are given data as 3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20 to create a tree containing these numbers. Now if our insert method takes the data in the order as given above, what will be the shape of our tree? Try to draw a sketch of the tree with some initial numbers in your mind. The tree will look like:

It does not seem to be a binary tree. Rather, it gives a look of a linked list, as there is a link from 3 to 4, a link from 4 to 5, a link from 5 to 7. Similarly while traversing the right link of the nodes, we reached at the node 20. There is no left child of any node. That’s why, it looks like a link list. What is the characteristic of the link list? In link list, every node has a pointer that points to the next node. While following this pointer, we can go to the next node. The root of this tree is 3. Now we have to find the node with value 20 in this tree. Remember that it is a tree, not a link list. We will use find method to search the number 20 in this tree. Now we will start from the root. As 20 is greater than 3, the recursive call to the method find will be made and we come to the next node i.e. 4. As 20 is greater than 4, so again a recursive call is generated. Similarly we will come to 5, then 7, 9 and so on. In the end, we will reach at 20 and the recursion will stop here.

Now if we search the above tree through the method in which we started from 3, then 4, 5 and so on, this will be the same technique as adopted in the link list. How much time it will take to find the number? We have seen in the link list that if the number to be searched is at the last node, a programmer will have to traverse all the nodes. This means that in case of nodes having strength of n, the loop will execute n times. Similarly as shown in the above tree, our find method will be called recursively equal to number of nodes in the tree. We have designed binary search tree in such a fashion that the search process is very short. You must be remembering the example of previous lecture that if we have one lakh numbers, it is possible to find the desired number in 20 iterations. If we have link list for one lakh elements, the required results can be obtained only after executing the loop for one lakh times if the element to be searched is the last element. However, in case of BST, there are only 20 steps. The BST technique, as witnessed earlier, is quite different as compared to this tree. They have both left and right subtrees. What happened with this tree? The benefit we have due to BST is not applicable here. It seems that it is a link list. This is only due to the fact that the data of the tree was given in the sorted order.

If you want to create a tree out of a sorted data with the insert method, it will look like the above tree. It means that you do not want to have sorted data. But it is not easy, as you might not have control over this process. Consider the example of polling. It is not possible that all the voters come to the polling station in some specific order. But in another example, if you are given a list of sorted data and asked to create a BST with this data. If you create a BST with data that is in an ascending order, it will look like a link list. In the link list, the search takes a lot of time. You have created a BST but the operations on it are working as it is a singly link list. How can we avoid that?

We know that the BST is very beneficial. One way to avoid this is that some how we get the sorted data unsorted. How this can be done. It is not possible, as data is not always provided as a complete set. Data is provided in chunks most of the times. Now what should we do? We will apply a technique here so that we can get the benefits of the BST. We should keep the tree balanced. In the above tree, nodes have left child and no right child. So this tree is not balanced. One way to achieve it is that both the left and right subtrees have the same height. While talking about the binary search tree, we discussed the height, depth and level of BST. Every node has some level. As we go down to the tree from the root, the levels of the tree increased and also the number of nodes, if all the left and right subtrees are present. You have earlier seen different examples of tree. The complete binary tree is such a tree that has all the left and right subtrees and all the leaf nodes in the end. In the complete binary tree, we can say that the number of nodes in the left subtree and right subtree are equal. If we weigh that tree on the balance, from the root, both of its sides will be equal as the number of nodes in the right subtree and left subtree are equal. If you have such a balanced binary search tree with one lakh nodes, there will need of only 20 comparisons to find a number. The levels of this tree are 20. We have also used the formula log₂ (100,000). The property of such a tree is that the search comparison can be computed with the help of log because subtrees are switched at every comparison.

Now let’s see the above tree which is like a singly link list. We will try to convert it into a balanced tree. Have a look on the following figure.

This tree seems to be a balanced tree. We have made 14 as the root. The nodes at the left side occur at the left of all the nodes i.e. left subtree of 14 is 9, the left subtree of 9 is 7, the left subtree of 7 is 5 and so on. Similarly the right subtree contains the nodes 15, 16, 17, 18, 20. This tree seems to be a balanced tree. Let’s see its level. The node 14 i.e. the root is at level zero. Then at level one, we have 9 and 15. At level two, there are 7 and 16. Then 5 and 17, followed by 4 and 18. In the end, we have 3 and 20. It seems that we have twisted the tree in the middle, taking 14 as a root node. If we take other nodes like 9 or 7, these have only left subtree. Similarly if we take 15 or 16, these have right subtrees only. These nodes do not have both right and left subtree. In the earlier example, we have seen that the nodes have right and left subtrees. In that example, the data was not sorted. Here the tree is not shallow. Still we can not get the required BST. What should we do? With the sorted data, the tree can not become complete binary search tree and the search is not optimized. We want the data in unsorted form that may not be available.

We want to make a balanced tree, keeping in mind that it should not be shallow one. We could insist that every node must have left and right subtrees of same height. But this requires that the tree be a complete binary tree. To achieve it, there must be (2^d+1 – 1) data items, where d is the depth of the tree. Here we are not pleading to have unsorted data. Rather, we need as much data which could help make a balanced binary tree. If we have a tree of depth d, there will be need of (2^d+1 – 1) data items i.e. we will have left and right subtrees of every node with the same height. Now think yourself that is it possible that whenever you build a tree or someone uses your BST class can fulfill this condition. This is not possible that whenever we are going to create a tree, there will be (2^d+1 – 1) data items for a tree of depth d. The reason is that most of the time you do not have control over the data. Therefore this is too rigid condition. So this is also not a practical solution.

 

AVL Tree

AVL tree has been named after two persons Adelson-Velskii and Landis. These two had devised a technique to make the tree balanced. According to them, an AVL tree is identical to a BST, barring the following possible differences:

• Height of the left and right subtrees may differ by at most 1.
• Height of an empty tree is defined to be (–1).

We can calculate the height of a subtree by counting its levels from the bottom. At some node, we calculate the height of its left subtree and right subtree and get the difference between them. Let’s understand this with the help of following fig.

This is an AVL tree. The root of the tree is 5. At next level, we have 2 and 8, followed by 1, 4 and 7 at next level where 1, 4 are left and right subtrees of node 2 and 7 is the left subtree of node 8. At the level three, we have 3. We have shown the levels in the figure at the right side. The root is at level 0, followed by the levels 1, 2 and 3. Now see the height of the left subtree of 5. It is 3. Similarly the height of the right subtree is 2. Now we have to calculate the difference of the height of left subtree and right subtree of 5. The height of left subtree of 5 is 3 and height of right subtree of 5 is 2. So the difference is 1. Similarly, we can have a tree in which right subtree is deeper than left subtree. The condition in the AVL tree is that at any node the height of left subtree can be one more or one less than the height of right subtree. These heights, of course, can be equal. The difference of heights can not be more than 1. This difference can be -1 if we subtract the height of left subtree from right subtree where the height of left subtree is one less than the height of right subtree. Remember that this condition is not at the root. It should satisfy at any level at any node. Let’s analyze the height of left subtree and right subtree of node 2. This should be -1, 0 or 1. The height of left subtree of node 2 is 1 while that of right subtree of the node 2 is 2. Therefore the absolute difference between them is 1. Similarly at node 8, the height of left subtree is 1 and right subtree does not exist so its height is zero. Therefore the difference is 1. At leaves, the height is zero, as there is no left or right subtree. In the above figure, the balanced condition is satisfactory at every level and node. Such trees have a special structure.

Let’s see another example. Here is the diagram of the tree.

The height of the left subtree of node 6 is three whereas the height of the right subtree is one. Therefore the difference is 2. The balanced condition is not satisfactory. Therefore, it is not an AVL tree.

Let’s give this condition a formal shape that will become a guiding principle for us while creating a tree. We will try to satisfy this condition during the insertion of a node in the tree or a deletion of a node from the tree. We will also see later how we can enforce this condition satisfactorily on our tree. As a result, we will get a tree whose structure will not be like a singly linked list.

The definition of height of a tree is:

• The height of a binary tree is the maximum level of its leaves (also called the depth).

The height of a tree is the longest path from the root to the leaf. This can also be calculated as the maximum level of the tree. If we have to calculate the height of some node, we should start counting the levels from that node.

The balance of a node is defined as:

• The balance of a node in a binary tree is defined as the height of its left subtree minus height of its right subtree.

Here, for example, is a balanced tree whose each node has an indicated balance of 1, 0, or –1.

In this example, we have shown the balance of each node instead of the data item. In the root node, there is the value -1. With this information, you know that the height of the right subtree at this node is one greater than that of the left subtree. In the left subtree of the root, we have node with value 1. You can understand from this example that the height of the right subtree at this node is one less than the height of the left subtree. In this tree, some nodes have balance -1, 0 or 1. You have been thinking that we have to calculate the balance of each node. How can we do that? When we create a tree, there will be a need of some information on the balance factor of each node. With the help of this information, we will try to balance the tree. So after getting this balance factor for each node, we will be able to create a balance tree even with the sorted data. There are other cases, which we will discuss, in the next lecture. In short, a balance tree with any kind of data facilitates the search process.

 

Explanation

In the year 1962, two Russian scientists, Adelson-Velskii and Landis, proposed the criteria to save the binary search tree (BST) from its degenerate form. This was an effort to propose the development of a balanced search tree by considering the height as a standard. This tree is known as AVL tree. The name AVL is an acronym of the names of these two scientists.

An AVL tree is identical to a BST, barring one difference i.e. the height of the left and right sub-trees can differ by at most 1. Moreover, the height of an empty tree is defined to be (–1).

Keeping in mind the idea of the level of a tree, we can understand that if the root of a tree is at level zero, its two children (subtrees) i.e. nodes will be at level 1. At level 2, there will be 4 nodes in case of a complete binary tree. Similarly at level 3, the number of nodes will be 8 and so on. As discussed earlier, in a complete binary tree, the number of nodes at any level k will be 2^k. We have also seen the level order traversal of a tree. The term height is identical to the level of a tree. Following is the figure of a tree in which level/height of nodes is shown.

Here in the figure, the root node i.e. 5 is at the height zero. The next two nodes 2 and 8 are at height (or level) 1. Then the nodes 1, 4 and 7 are at height 2 i.e. two levels below the root. At the last, the single node 3 is at level (height) 3. Looking at the figure, we can say that the maximum height of the tree is 3. AVL states that a tree should be formed in such a form that the difference of the heights (maximum no of levels i.e. depth) of left and right sub-trees of a node should not be greater than 1. The difference between the height of left subtree and height of right subtree is called the balance of the node. In an AVL tree, the balance (also called balance factor) of a node will be 1,0 or –1 depending on whether the height of its left subtree is greater than, equal to or less than the height of its right subtree.

Now consider the tree in the figure 20.1. Its root node is 5. Now go to its left subtree and find the deepest node in this subtree. We see that node 3 is at the deepest level. The level of this deepest node is 3, which means the height of this left subtree is 3. Now from node 5, go to its right subtree and find the deepest level of a node. The node 7 is the deepest node in this right subtree and its level is 2. This means that the height of right subtree is 2. Thus the difference of height of left subtree (i.e. 3) and height of right subtree (i.e. 2) is 1. So according to the AVL definition, this tree is balanced one. But we know that the AVL definition does not apply only to the root node of the tree. Every node (non-leaf or leaf) should fulfill this definition. This means that the balance of every node should be 1, 0 or –1. Otherwise, it will not be an AVL tree.

Now consider the node 2 and apply the definition on it. Let’s see the result. The left subtree of node 2 has the node 1 at deepest level i.e. level 2. The node 2, itself, is at level 1, so the height of the left subtree of node 2 is 2-1 i.e. 1. Now look at the right subtree of node 2. The deepest level of this right subtree is 3 where the node 3 exists. The height of this right subtree of node 2 will be 3 –1 = 2 as the level of node 2 is 1. Now the difference of the height of left subtree (i.e. 1) and height of the right subtree (i.e. 2) is –1. We subtract the height of left subtree from the height of the right subtree and see that node 2 also fulfills the AVL definition. Similarly we can see that all other nodes of the tree (figure 20.1) fulfill the AVL definition. This means that the balance of each node is 1, 0 or –1. Thus it is an AVL tree, also called the balanced tree. The following figure shows the tree with the balance of each node.

Let’s consider a tree where the condition of an AVL tree is not being fulfilled. The following figure shows such a tree in which the balance of a node (that is root node 6) is greater than 1. In this case, we see that the left subtree of node 6 has height 3 as its deepest nodes 3 and 5 are at level 3. Whereas the height of its right subtree is 1 as the deepest node of right subtree is 8 i.e. level 1. Thus the difference of heights (i.e. balance) is 2. But according to AVL definition, the balance should be1, 0 or –1. As shown in the figure, this node 6 is only the node that violates the AVL definition (as its balance is other than 1, 0 and -1). The other nodes fulfill the AVL definition. We know that to be an AVL tree, each node of the tree should fulfill the definition. Here in this tree, the node 6 violates this definition so this is not an AVL tree.

From the above discussion, we encounter two terms i.e. height and balance which can be defined as under.

Height

The height of a binary tree is the maximum level of its leaves. This is the same definition as of depth of a tree.

Balance

The balance of a node in a binary search tree is defined as the height of its left subtree minus height of its right subtree. In other words, at a particular node, the difference in heights of its left and right subtree gives the balance of the node.

The following figure shows a balanced tree. In this figure the balance of each node is shown along with. We can see that each node has a balance 1, 0 or –1.

Here in the figure, we see that the balance of the root (i.e. node 6) is –1. We can find out this balance. The deepest level of the left subtree is 3 where the nodes 1 and 3 are located. Thus the height of left subtree is 3. In the right subtree, we see some leaf nodes at level 3 while some are found at level 4. But we know that the height of the tree is the maximum level. So 4 is the height of the right subtree. Now we know that the balance of the root node will be the result of height of left subtree minus the height of right subtree. Thus the balance of the root node is 3 – 4 = -1. Similarly we can confirm the balance of other nodes. The confirmation of balance of the other nodes of the tree can be done. You should do it as an exercise. The process of height computation should be understood as it is used for the insertion and deletion of nodes in an AVL tree. We may come across a situation, when the tree does not remain balanced due to insertion or deletion. For making it a balanced one, we have to carry out the height computations.

While dealing with AVL trees, we have to keep the information of balance factor of the nodes along with the data of nodes. Similarly, a programmer has to have additional information (i.e. balance) of the nodes while writing code for AVL tree.

Insertion of Node in an AVL Tree

Now let’s see the process of insertion in an AVL tree. We have to take care that the tree should remain AVL tree after the insertion of new node(s) in it. We will now see how an AVL tree is affected by the insertion of nodes.

We have discussed the process of inserting a new node in a binary search tree in previous lectures. To insert a node in a BST, we compare its data with the root node. If the new data item is less than the root node item in a particular order, this data item will hold its place in the left subtree of the root. Now we compare the new data item with the root of this left subtree and decide its place. Thus at last, the new data item becomes a leaf node at a proper place. After inserting the new data item, if we traverse the tree with the inorder traversal, then that data item will become at its appropriate position in the data items. To further understand the insertion process, let’s consider the tree of figure 20.4. The following figure (Fig 20.5) shows the same tree with the difference that each node shows the balance along with the data item. We know that a new node will be inserted as a leaf node. This will be inserted where the facility of adding a node is available. In the figure, we have indicated the positions where a new node can be added. We have used two labels B and U for different positions where a node can be added. The label B indicates that if we add a node at this position, the tree will remain balanced tree. On the other hand, the addition of a node at the position labeled as U1, U2 ….U12, the tree will become unbalanced. That means that at some node the difference of heights of left and right subtree will become greater than 1.

By looking at the labels B, U1, U2 …….U12, we conclude some conditions that will be implemented while writing the code for insert method of a balanced tree.

We may conclude that the tree becomes unbalanced only if the newly inserted node

• Is a left descendent of a node that previously had a balance of 1

(in the figure 20.5 these positions are U1, U2 …..U8)

• Or is a descendent of a node that previously had a balance of –1

(in the tree in fig 20.5 these positions are U9, U10, U11 and U12)

The above conditions are obvious. The balance 1 of a node indicates that the height of its left subtree is 1 more than the height of its right subtree. Now if we add a node to this left subtree, it will increase the level of the tree by 1. Thus the difference of heights will become 2. It violates the AVL rule, making the tree unbalanced.

Similarly the balance –1 of a node indicates that the right subtree of this node is one level deep than the left subtree of the node. Now if the new node is added in the right subtree, this right subtree will become deeper. Its depth/height will increase as a new node is added at a new level that will increase the level of the tree and the height. Thus the balance of the node, that previously has a balance –1, will become –2.

The following figure (Fig 20.6) depicts this rule. In this figure, we have associated the new positions with their grand parent. The figure shows that U1, U2, U3 and U4 are the left descendents of the node that has a balance 1. So according to the condition, the insertion of new node at these positions will unbalance the tree. Similarly the positions U5, U6, U7 and U8 are the left descendents of the node that has a balance 1. Moreover we see that the positions U9, U10, U11 and U12 are the right descendents of the node that has balance –1. So according to the second condition as stated earlier, the insertion of a new node at these positions would unbalance the tree.

Now let’s discuss what should we do when the insertion of a node makes the tree unbalanced. For this purpose, consider the node that has a balance 1 in the previous tree. This is the root of the left subtree of the previous tree. This tree is shown as shaded in the following figure.

We will now focus our discussion on this left subtree of node having balance 1 before applying it to other nodes. Look at the following figure (Fig 20.8). Here we are talking about the tree that has a node with balance 1 as the root. We did not mention the other part of the tree. We indicate the root node of this left subtree with label A. It has balance 1. The label B mentions the first node of its left subtree. Here we did not mention other nodes individually. Rather, we show a triangle that depicts all the nodes in subtrees. The triangle T3 encloses the right subtree of the node A. We are not concerned about the number of nodes in it. The triangles T1 and T2 mention the left and right subtree of the B node respectively. The balance of node B is 0 that describes that its left and right subtrees are at same height. This is also shown in the figure. Similarly we see that the balance of node A is 1 i.e. its left subtree is one level deep than its right subtree. The dotted lines in the figure show that the difference of depth/height of left and right subtree of node A is 1 and that is the balance of node A.

Now considering the notations of figure 20.8, let’s insert a new node in this tree and observe the effect of this insertion in the tree. The new node can be inserted in the tree T1, T2 or T3. We suppose that the new node goes to the tree T1. We know that this new node will not replace any node in the tree. Rather, it will be added as a leaf node at the next level in this tree (T1). The following figure (fig 20.9) shows this phenomenon.

Due to the increase of level in T1, its difference with the right subtree of node A (i.e. T3) will become 2. This is shown with the help of dotted line in the above figure. This difference will affect the balances of node A and B. Now the balance of node A becomes 2 while balance of node B becomes 1. These new balances are also shown in the figure. Now due to the balance of node A (that is 2), the AVL condition has been violated. This condition states that in an AVL tree the balance of a node cannot be other than 1, 0 or –1. Thus the tree in fig 20.9 is not a balanced (AVL) tree.

Now the question arises what a programmer should do in case of violation of AVL condition .In case of a binary search tree, we insert the data in a particular order. So that at any time if we traverse the tree with inorder traversal, only sorted data could be obtained. The order of the data depends on its nature. For example, if the data is numbers, these may be in ascending order. If we are storing letters, then A is less than B and B is less than C. Thus the letters are generally in the order A, B, C ……. This order of letters is called lexographic order. Our dictionaries and lists of names follow this order.

If we want that the inorder traversal of the tree should give us the sorted data, it will not be necessary that the nodes of these data items in the tree should be at particular positions. While building a tree, two things should be kept in mind. Firstly, the tree should be a binary tree. Secondly, its inorder traversal should give the data in a sorted order. Adelson-Velskii and Landis considered these two points

. They said that if we see that after insertion, the tree is going to be unbalanced. Then the things should be reorganized in such a way that the balance of nodes should fulfill the AVL condition. But the inorder traversal should remain the same.

Now let’s see the example of tree in figure 20.9 and look what we should do to balance the tree in such a way that the inorder traversal of the tree remains the same. We have seen in figure 20.9 that the new node is inserted in the tree T1 as a new leaf node. Thus T1has been modified and its level is increased by 1. Now due to this, the difference of T1 and T3 is 2. This difference is the balance of node A as T1 and T3 are its left and right subtrees respectively. The inorder traversal of this tree gives us the result as given below.

T1 B T2 A T3

Now we rearrange the tree and it is shown in the following figure i.e. Fig 20.10.

By observing the tree in the above figure we notice at first that node A is no longer the root of the tree. Now Node B is the root. Secondly, we see that the tree T2 that was the right subtree of B has become the left subtree of A. However, tree T3 is still the right subtree of A. The node A has become the right subtree of B. This tree is balanced with respect to node A and B. The balance of A is 0 as T2 and T3 are at the same level. The level of T1 has increased due to the insertion of new node. It is now at the same level as that of T2 and T3. Thus the balance of B is also 0. The important thing in this modified tree is that the inorder traversal of it is the same as in the previous tree (fig 10.9) and is

T1 B T2 A T3

We see that the above two trees give us data items in the same order by inorder traversal. So it is not necessary that data items in a tree should be in a particular node at a particular position. This process of tree modification is called rotation.

Example (AVL Tree Building)

Let’s build an AVL tree as an example. We will insert the numbers and take care of the balance of nodes after each insertion. While inserting a node, if the balance of a node becomes greater than 1 (that means tree becomes unbalance), we will rearrange the tree so that it should become balanced again. Let’s see this process.

Assume that we have insert routine (we will write its code later) that takes a data item as an argument and inserts it as a new node in the tree. Now for the first node, let’s say we call insert (1). So there is one node in the tree i.e. 1. Next, we call insert (2). We know that while inserting a new data item in a binary search tree, if the new data item is greater than the existing node, it will go to the right subtree. Otherwise, it will go to the left subtree. In the call to insert method, we are passing 2 to it. This data item i.e. 2 is greater than 1. So it will become the right subtree of 1 as shown below.

As there are only two nodes in the tree, there is no problem of balance yet.

Now insert the number 3 in the tree by calling insert (3). We compare the number 3 with the root i.e.1. This comparison results that 3 will go to the right subtree of 1. In the right subtree of 1 there becomes 2. The comparison of 3 with it results that 3 will go to the right subtree of 2. There is no subtree of 2, so 3 will become the right subtree of 2. This is shown in the following figure.

Let’s see the balance of nodes at this stage. We see that node 1 is at level 0 (as it is the root node). The nodes 2 and 3 are at level 1 and 2 respectively. So with respect to the node 1, the deepest level (height) of its right subtree is 2. As there is no left subtree of node 1 the level of left subtree of 1 is 0. The difference of the heights of left and right subtree of 1 is –2 and that is its balance. So here at node 1, the AVL condition has been violated. We will not insert a new node at this time. First we will do the rotation to make the tree (up to this step) balanced. In the process of inserting nodes, we will do the rotation before inserting next node at the points where the AVL condition is being violated. We have to identify some things for doing rotation. We have to see that on what nodes this rotation will be applied. That means what nodes will be rearranged. Some times, it is obvious that at what nodes the rotation should be done. But there may situations, when the things will not be that clear. We will see these things with the help of some examples.

In the example under consideration, we apply the rotation at nodes1 and 2. We rotate these nodes to the left and thus the node 1 (along with any tree if were associated with it) becomes down and node 2 gets up. The node 3 (and trees associated with it, here is no tree as it is leaf node) goes one level upward. Now 2 is the root node of the tree and 1 and 3 are its left and right subtrees respectively as shown in the following figure.

We see that after the rotation, the tree has become balanced. The figure reflects that the balance of node 1, 2 and 3 is 0. We see that the inorder traversal of the above tree before rotation (tree on left hand side) is 1 2 3. Now if we traverse the tree after rotation (tree on right hand side) by inorder traversal, it is also 1 2 3. With respect to the inorder traversal, both the traversals are same. So we observe that the position of nodes in a tree does not matter as long as the inorder traversal remains the same. We have seen this in the above figure where two different trees give the same inorder traversal. In the same way we can insert more nodes to the tree. After inserting a node we will check the balance of nodes whether it violates the AVL condition. If the tree, after inserting a node, becomes unbalance then we will apply rotation to make it balance. In this way we can build a tree of any number of nodes.

Let’s see the tree’s figures below:

Node containing number 2 became the root node after the rotation of the node having number 1. Note the direction of rotation here.

Let’s insert few more nodes in the tree. We will build an AVL tree and rotate the node when required to fulfill the conditions of an AVL tree.

To insert a node containing number 4,we will, at first, compare the number inside the root node. The current root node is containing number 2. As 4 is greater than 2, it will take the right side of the root. In the right subtree of the root, there is the node containing number 3. As 4 is also greater than 3, it will become the right child of the node containing number 3.

Once we insert a node in the tree, it is necessary to check its balance to see whether it is within AVL defined balance. If it is not so, then we have to rotate a node. The balance factor of the node containing number 4 is zero due to the absence of any left or right subtrees. Now, we see the balance factor of the node containing number 3. As it has no left child, but only right subtree, the balance factor is –1. The balance factor of the node containing number 1 is 0. For the node containing number 2, the height of the left subtree is 1 while that of the right subtree is 2. Therefore, the balance factor of the node containing number 2 is 1 – 2 = -1. So every node in the tree in fig. 21.3 has balance factor either 1 or less than that. You must be remembering that the condition for a tree to be an AVL tree, every node’s balance needs not to be zero necessarily. Rather, the tree will be called AVL tree, if the balance factor of each node in a tree is 0, 1 or –1. By the way, if the balance factor of each node inside the tree is 0, it will be a perfectly balanced tree.

Next, we insert a node containing number 5 and see the balance factor of each node. The balance factor for the node containing 5 is 0. The balance factor for node containing 4 is –1 and for the node containing 3 is -2. The condition for AVL is not satisfied here for the node containing number 3, as its balance factor is –2. The rotation operation will be performed here as with the help of an arrow as shown in the above Fig 21.4. After rotating the node 3, the new tree will be as under:

You see in the above figure that the node containing number 4 has become the right child of the node containing number 2. The node with number 3 has been rotated. It has become the left child of the node containing number 4. Now, the balance factor for different nodes containing numbers 5, 3 and 4 is 0. To get the balance factor for the node containing number 2, we see that the height of the left subtree containing number 2 is 1 while height of the right subtree is 2. So the balance factor of the node containing number 2 is –1. We saw that all the nodes in the tree above in Fig 21.5 fulfill the AVL tree condition.

If we traverse the tree Fig 21.5, in inorder tree traversal, we get:

1 2 3 4 5

Similarly, if we traverse the tree in inorder given in Fig 21.4 (the tree before we had rotated the node containing number 3), following will be the output.

1 2 3 4 5

In both the cases above, before and after rotation, we saw that the inorder traversal of trees gives the same result. Also the root (node containing number 2) remained the same.

See the Fig 21.4 above. Considering the inorder traversal, we could arrange the tree in such a manner that node 3 becomes the root of the tree, node 2 as the left child of node 3 and node 1 as the left child of the node 2. The output after traversing the changed tree in inorder will still produce the same result:

1 2 3 4 5

While building an AVL tree, we rotate a node immediately after finding that that the node is going out of balance. This ensures that tree does not become shallow and remains within the defined limit for an AVL tree.

Let’s insert another element 6 in the tree. The figure of the tree becomes:

The newly inserted node 6 becomes the right child of the node 5. Usually, after the insertion of a node, we will find out the node factor for each node and rotate it immediately. This is carried out after finding the difference out of limit. The balance factor for the node 6 is 0, for node 5 is –1 and 0 for node 3. Node 4 has –1 balance factor and node 1 has 0. Finally, we check the balance factor of the root node, node 2, the left subtree’s height is 1 and the right subtree’s height is 3. Therefore, the balance factor for node 2 is –2, which necessitates the rotation of the root node 2. Have a look on the following figure to see how we have rotated the node 2.

Now the node 4 has become the root of the tree. Node 2, which was the root node, has become the left child of node 4. Nodes 5 and 6 are still on their earlier places while remaining the right child and sub-child of node 4 respectively. However, the node 3, which was left child of node 4, has become the right child of node 2.

Now, let’s see the inorder traversal of this tree:

1 2 3 4 5 6

You are required to practice this inorder traversal. It is very important and the basic point of performing the rotation operation is to preserve the inorder traversal of the tree. There is another point to note here that in Binary Search Tree (BST), the root node remains the same (the node that is inserted first). But in an AVL tree, the root node keeps on changing.

In Fig 21.6: we had to traverse three links (node 2 to node 4 and then node 5) to reach the node 6. While after rotation, (in Fig 21.7), we have to traverse the two links (node 4 and 5) to reach the node 6. You can prove it mathematically that inside an AVL tree built of n items; you can search up to 1.44log₂n levels to find a node inside. After this maximum number of links traversal, a programmer will have success or failure, as 1.44log₂n is the maximum height of the AVL tree. Consider the BST case, where we had constructed a linked list. If we want to build a BST of these six numbers, a linked list structure is formed. In order to reach the node 6, we will have to traverse five links. In case of AVL tree, we had to traverse two links only.

Let’s add few more items in the AVL tree and see the rotations performed to maintain AVL characteristics of the tree.

Node 7 is inserted as the right child of node 6. We start to see the balance factors of the nodes. The balance factors for node 7, 6 are 0 and –1 respectively. As the balance factor for node 5 is –2, the rotation will be performed on this node. After rotation, we get the tree as shown in the following figure.

After the rotation, node 5 has become the left child of node 6. We can see in the Fig 21.9 that the tree has become the perfect binary tree. While writing our program, we will have to compute the balance factors of each node to know that the tree is a perfectly balanced binary tree. We find that balance factor for all nodes 7, 5, 3, 1, 6, 2 and 4 is 0. Therefore, we know that the tree is a perfect balanced tree. Let’ see the inorder traversal output here:

1 2 3 4 5 6 7

It is still in the same sequence and the number 7 has been added at the end.

We have inserted a new node 16 in the tree as shown in the above Fig 21.10. This node has been added as the right child of the node 7. Now, let’s compute the balance factors for the nodes. The balance factor for nodes 16, 7, 5, 3, 1, 6, 2 and 4 is either 0 or –1. So this fulfills the condition of a tree to be an AVL. Let’s insert another node containing number 15 in this tree. The tree becomes as given in the figure below:

Next step is to find out the balance factor of each node. The factors for nodes 5 and 16 are 0 and 1 respectively. This is within limits of an AVL tree but the balance factor for node 7 is –2. As this is out of the limits of AVL, we will perform the rotation operation here. In the above diagram, you see the direction of rotation. After rotation, we have the following tree:

Node 7 has become the left child of node 16 while node 15 has attained the form of the right child of node 7. Now the balance factors for node 15, 7 and 16 are 0, -1 and 2 respectively. Note that the single rotation above when we rotated node 7 is not enough as our tree is still not an AVL one. This is a complex case that we had not encountered before in this example.

Technorati Tags: ds tutorial,data structure tutorial,tree data structure,trees in data structure,tree ds,tree traversal data structure,tree types,types of trees,binary trees,binary search trees,bst,bst data structure,bst ds,complete binary search tree,non tree structure,linear tree,avl tree,avl tree traversal,avl data structure,avl ds,avl tree rotation,rotation of avl tree,avl tree tutorial

Deleting a Node From Binary Search Tree

 

Until now, we have been discussing about adding data elements in a binary tree but we may also require to delete some data (nodes) from a binary tree. Consider the case where we used binary tree to implement the telephone directory, when a person leaves a city, its telephone number from the directory is deleted.

It is common with many data structures that the hardest operation is deletion. Once we have found the node to be deleted, we need to consider several possibilities.

For case 1, If the node is a leaf, it can be deleted quite easily.

See the tree figure below.

Suppose we want to delete the node containing number 3, as it is a leaf node, it is pretty straight forward. We delete the leaf node containing value 3 and point the right subtree pointer to NULL.

For case 2, if the node has one child, the node can be deleted after its parent adjusts a pointer to bypass the node and connect to inorder successor.

If we want to delete the node containing number 4 then we have to adjust the right subtree pointer in the node containing value 2 to the inorder successor of 4. The important point is that the inorder traversal order has to be maintained after the delete.

The case 3 is bit complicated, when the node to be deleted has both left and right subtrees.

The strategy is to replace the data of this node containing the smallest data of the right subtree and recursively delete that node.

Let’s see this strategy in action. See the tree below:

In this tree, we want to delete the node containing number 2. Let’s do inorder traversal of this tree first. The inorder traversal give us the numbers: 1, 2, 3, 4, 5, 6 and 8.

In order to delete the node containing number 2, firstly we will see its right subtree and find the left most node of it.

The left most node in the right subtree is the node containing number 3. Pay attention to the nodes of the tree where these numbers are present. You will notice that node containing number 3 is not right child node of the node containing number 2 instead it is left child node of the right child node of number 2. Also the left child pointer of node containing number 3 is NULL.

After we have found the left most node in the right subtree of the node containing number 2, we copy the contents of this left most node i.e. 3 to the node to be deleted with number 2.

Next step is to delete the left most node containing value 3. Now being the left most node, there will be no left subtree of it, it might have a right subtree. Therefore, the deletion of this node is the case 2 deletion and the delete operation can be called recursively to delete the node.

Now if we traverse the tree in inorder, we get the numbers as: 1, 3, 4, 5, 6 and 8. Notice that these numbers are still sorted.

Technorati Tags: ds tutorial,data structure tutorial,tree data structure,trees in data structure,tree ds,tree traversal data structure,tree types,types of trees,binary trees,binary search trees,bst,bst data structure,bst ds,complete binary search tree,non tree structure,linear tree,binary search tree,deleting a node from bst,deleting node binary search tree

Binary Search Tree

The advantages of the tree data structure over linked list data structure are many. In a linked list, a programmer has to search the whole list to find out a duplicate of a number to be inserted. It is very tedious job as the number of stored items in a linked list is very large. But in case of tree data structure, we get a dynamic structure in which any number of items as long as memory is available, can be stored. By using tree data structure, the search operation can be carried out very fast. Now we will see how the use of binary tree can help in searching the duplicate number in a very fast manner.

 

Cost of Search

Consider the previous example where we inserted the number 17 in the tree. We executed a while loop in the insert method and carried out a comparison in while loop. If the comparison is true, it will reflect that in this case, the number in the node where the pointer p is pointing is not equal to 17 and also q is not NULL. Then we move p actually q to the left or right side. This means that if the condition of the while loop is true then we go one level down in the tree. Thus we can understand it easily that if there is a tree of 6 levels, the while loop will execute maximum 6 times. We conclude from it that in a given binary tree of depth d, the maximum number of executions of the while loop will be equal to d. The code after the while loop will do the process depending upon the result of the while loop. It will insert the new number or display a message if the number was already there in the tree.

Now suppose we have another method find. This method does not insert a new number in the tree. Rather, it traverses a tree to find if a given number is already present in the tree or not. The tree which the find method traverses was made in such an order that all the numbers less than the number at the root are in the left sub-tree of the root while the right sub-tree of the root contains the numbers greater than the number at the root. Now the find method takes a number x and searches out its duplicate in the given tree. The find method will return true if x is present in the tree. Otherwise, it will return false. This find method does the same process that a part of the insert method performs. The difference is that the insert method checks for a duplicate number before putting a number in the tree whereas the find method only finds a number in the tree. Here in the find method, the while loop is also executed at maximum equal to the number of levels of the tree. We do a comparison at each level of the tree until either x is found or q becomes NULL. The loop terminates in case, the number is found or it executes to its maximum number, i.e. equal to the number of levels of the tree.

In the discussion on binary tree, we talked about the level and number of nodes of a binary tree. It was witnessed that if we have a complete binary tree with n numbers of nodes, the depth d of the tree can be found by the following equation:

d = log₂ (n + 1) – 1

Suppose we have a complete binary tree in which there are 100,000 nodes, then its depth d will be calculated in the following fashion.

d = log₂ (100000 + 1) – 1 = log₂ (100001) – 1= 20

The statement shows that if there are 100,000 unique numbers (nodes) stored in a complete binary tree, the tree will have 20 levels. Now if we want to find a number x in this tree (in other words, the number is not in the tree), we have to make maximum 20 comparisons i.e. one comparison at each level. Now we can understand the benefit of tree as compared to the linked list. If we have a linked list of 100,000 numbers, then there may be 100,000 comparisons (supposing the number is not there) to find a number x in the list.

Thus in a tree, the search is very fast as compared to the linked list. If the tree is complete binary or near-to-complete, searching through 100,000 numbers will require a maximum of 20 comparisons or in general, approximately log₂(n). Whereas in a linked list, the comparisons required could be a maximum of n.

Tree with the linked structure, is not a difficult data structure. We have used it to allocate memory, link and set pointers to it. It is not much difficult process. In a tree, we link the nodes in such a way that it does not remain a linear structure. If instead of 100,000, we have 1 million or 10 million or say, 1 billion numbers and want to build a complete binary tree of these numbers, the depth (number of levels) of the tree will be log₂ of these numbers. The log₂ of these numbers will be a small number, suppose 25, 30 or 40. Thus we see that the number of level does not increase in such a ratio as the number of nodes increase. So we can search a number x in a complete binary tree of 1 billion nodes only in 30-40 comparisons. As the linked list of such a large number grows large, the search of a number in such a case will also get time consuming process. The usage of memory space does not cause any effect in the linked list and tree data structures. We use the memory dynamically in both structures. However, time is a major factor. Suppose one comparison takes one micro second, then one billion seconds are required to find a number from a linked list (we are supposing the worst case of search where traversing of the whole list may be needed). This time will be in hours. On the other hand, in case of building a complete binary tree of these one billion numbers, we have to make 30-40 comparisons (as the levels of the tree will be 30-40), taking only 30-40 microseconds. We can clearly see the difference between hours and microseconds. Thus it is better to prefer the process of building a tree of the data to storing it in a linked list to make the search process faster.

 

Binary Search Tree

While discussing the search procedure, the tree for search was built in a specific order. The order was such that on the addition of a number in the tree, we compare it with a node. If it is less than this, it can be added to the left sub-tree of the node. Otherwise, it will be added on the right sub-tree. This way, the tree built by us has numbers less than the root in the left sub-tree and the numbers greater than the root in the right sub-tree. A binary tree with such a property that items in the left sub-tree are smaller than the root and items in the right sub-tree are larger than the root is called a binary search tree (BST). The searching and sorting operations are very common in computer science. We will be discussing them many times during this course. In most of the cases, we sort the data before a search operation. The building process of a binary search tree is actually a process of storing the data in a sorted form. The BST has many variations, which will be discussed later. The BST and its variations play an important role in searching algorithms. As data in a BST is in an order, it may also be termed as ordered tree.

 

Traversing a Binary Tree

Now let’s discuss the ways to print the numbers present in a BST. In a linked list, the printing of stored values is easy. It is due to the fact that we know wherefrom, a programmer needs to start and where the next element is. Equally is true about printing of the elements in an array. We execute a for loop starting from the first element (i.e. index 0) to the last element of the array. Now let’s see how we can traverse a tree to print (display) the numbers (or any data items) of the tree.

We can explain this process with the help of the following example in which we traverse a binary search tree. Suppose there are three nodes tree with three numbers stored in it as shown below.

Fig 13.1: A three node binary tree

Here we see that the root node has the number 14. The left sub-tree has only one node i.e. number 4. Similarly the right sub-tree consists of a single node with the number 15. If we apply the permutations combinations on these three nodes to print them, there may be the following six possibilities.

1: (4, 14, 15)

2: (14, 4, 15)

3: (15, 4, 14)

4: (4, 15, 14)

5: (14, 15, 4)

6: (15, 14, 4)

Look at these six combinations of printing the nodes of the tree. In the first combination, the order of printing the nodes is 4-14-15. It means that left subtree-root-right subtree. In the second combination the order is root-left subtree-right subtree. In the third combination, the order of printing the nodes is right subtree-root-left subtree. The fourth combination has left subtree-right subtree-root. The fifth combination has the order root-rigth subtree- left subtree. Finally the sixth combination has the order of printing the nodes right subtree-root-left subtree. These six possibilities are for the three nodes only. If we have a tree having a large number of nodes, then there may increase number of permutations for printing the nodes.

Let’s see the general procedure of traversing a binary tree. We know by definition that a binary tree consists of three sets i.e. root, left subtree and right subtree. The following figure depicts a general binary tree.

Fig 13.2: A generic binary tree

In this figure, we label the root node with N. The left subtree in the figure is in a triangle labeled as L. This left subtree may consist of any number of nodes. Similarly the right subtree is enclosed in a triangle having the label R. This triangle of right subtree may contain any number of nodes. Following are the six permutations, which we have made for the three nodes previously. To generalize these permutations, we use N, L and R as abbreviations for root, left subtree and right subtree respectively.

1: (L, N, R)

2: (N, L, R)

3: (R, L, N)

4: (L, R, N)

5: (N, R, L)

6: (R, N, L)

In these permutations, the left and right subtree are not single nodes. These may consist of several nodes. Thus where we see L in the permutations, it means traversing the left subtree. Similarly R means traversing the right subtree. In the previous tree of three nodes, these left and right subtrees are of single nodes. However, they can consist of any number of nodes. We select the following three permutations from the above six. The first of these three is (N, L, R), also called as preorder traversal. The second permutation is (L, N, R) which we called inorder traversal. Finally the third permutation, also termed as postorder traversal is (L, R, N). Now we will discuss these preorder, inorder and postorder traversal in detail besides having a look on their working. We will also see the order in which the numbers in the tree are displayed by these traversing methods.

C++ code

Let’s write the C++ code for it. Following is the code of the preorder method.

void preorder(TreeNode<int>* treeNode) { if( treeNode != NULL ) { cout << *(treeNode->getInfo())<<" "; preorder(treeNode->getLeft()); preorder(treeNode->getRight()); } }

In the arguments, there is a pointer to a TreeNode. We may start from any node and the pointer of the node will be provided as argument to the preorder method. In this method, first of all we check whether the pointer provided is NULL or not. If it is not NULL, we print the information stored in that node with the help of the getInfo() method. Then we call the getLeft() method that returns a pointer of left node, which may be a complete subtree. With the help of this method, we get the root of that subtree. We call the preorder method again passing that pointer. When we return from that, the preorder method is called for the right node. Let’s see what is happening in this method. We are calling the preorder method within the preorder method. This is actually a recursive call. Recursion is supported in C++ and other languages. Recursion means that a function can call itself. We may want to know why we are doing this recursive call. We will see some more examples in this regard and understand the benefits of recursive calls. For the time being, just think that we are provided with a tree with a root pointer. In the preorder, we have to print the value of the root node. Don’t think that you are in the preorder method. Rather keep in mind that you have a preorder function. Suppose you want to print out the left subtree in the preorder way. For this purpose, we will call the preorder function. When we come back, the right subtree will be printed. In the right subtree, we will again call the preorder function that will print the information. Then call the preorder function for the left subtree and after that its right subtree. It will be difficult if you try to do this incursion in the mind. Write the code and execute it. You must be knowing that the definition of the binary tree is recursive. We have a node and left and right subtrees. What is left subtree? It is also a node with a left subtree and right subtree. We have shown you how the left subtree and right subtree are combined to become a tree. The definition of tree is itself recursive. You have already seen the recursive functions. You have seen the factorial example. What is factorial of N? It is N multiplied by N-1 factorial. What is N-1 factorial? N-1 factorial is N-1 multiplied by N-2 factorial. This is the recursive definition. For having an answer, it is good to calculate the factorial of one less number till the time you reach at the number 2. You will see these recursions or recursive relations here and also in mathematic courses. In the course of discrete mathematics, recursion method is used. Here we are talking about the recursive calls. We will now see an example to understand how this recursive call works and how can we traverse the tree using the recursion. One of the benefits of recursion that it prints out the information of all the nodes without caring for the size of the tree. If the tree has one lakh nodes, this simple four lines routine will print all the nodes. When compared with the array printing, we have a simple loop there. In the link list also, we have a small loop that executes till the time we have a next pointer as NULL. For tree, we use recursive calls to print it.

Here is the code of the inorder function.

void inorder(TreeNode<int>* treeNode) { if( treeNode != NULL ) { inorder(treeNode->getLeft()); cout << *(treeNode->getInfo())<<" "; inorder(treeNode->getRight()); } }

The argument is the same as in the preorder i.e. a pointer to the TreeNode. If this node is not NULL, we call getLeft() to get the left node and call the inorder function. We did not print the node first here. In the inorder method, there is no need to print the root tree first of all. We start with the left tree. After completely traversing the complete left tree, we print the value of the node. In the end, we traverse the right subtree in recursion.

Hopefully, you have now a fair knowledge about the postorder mechanism too. Here is the code of the postorder method.

void postorder(TreeNode<int>* treeNode) { if( treeNode != NULL ) { postorder(treeNode->getLeft()); postorder(treeNode->getRight()); cout << *(treeNode->getInfo())<<" "; } }

In the postorder, the input argument is a pointer to the TreeNode. If the node is not NULL, we traverse the left tree first. After that we will traverse the right tree and print the node value from where we started.

As all of these above routines are function so we will call them as:

cout << "inorder: "; preorder( root); cout << "inorder: "; inorder( root ); cout << "postorder: "; postorder( root );

Here the root represents the root node of the tree. The size of the tree does not matter as the complete tree will be printed in preorder, inorder and postorder. Let’s discuss an example to see the working of these routines.

Example

Let’s have a look on the following tree.

3 5 7 9 4 17 16 20 18 15 14

This is the same tree we have been using previously. Here we want to traverse the tree. In the bottom of the figure, the numbers are printed with the help of preorder method. These numbers are as 14 4 3 9 7 5 15 18 16 17 20. Now take these numbers and traverse the tree. In the preorder method, we print the root, followed by traversing of the left subtree and the right subtree respectively. As the value of the root node is 14, so it will be printed first of all. After printing the value of the root node, we call the preorder for the left node which is 4. Forget the node 14 as the root is 4 now. So the value 4 is printed and we call the preorder again with the left sub tree i.e. the node with value 3. Now the root is the node with value 3. We will print its value before going to its left. The left side of node with value 3 is NULL. Preorder will be called if condition is false. In this case, no action will be taken. Now the preorder of the left subtree is finished. As the right subtree of this node is also NULL, so there is no need of any action. Now the left subtree of the node with value 4 is complete. The method preorder will be called for the right subtree of the node with value 4. So we call the preorder with the right node of the node with value 4. Here, the root is the node with value 9 that is printed. We will call its left subtree where the node value is 7. It will be followed by its left subtree i.e. node 5 which will be printed.

In the preorder method, we take the root i.e. 14 in this case. Its value is printed, followed by its left subtree and so on. This activity takes us to the extreme left node. Then we back track and print the right subtrees.

Let’s try to understand the inorder method from the following statement.

When we call the inorder function, the numbers will be printed as 3 4 5 7 9 14 15 16 17 18 20. You might have noted that these numbers are in sorted order. When we build the tree, there was no need of sorting the numbers. But here we have the sorted numbers in the inorder method. While inserting a new node, we compare it with the existing ones and place the new node on the left or right side. So during the process of running the inorder on the binary tree, a programmer gets the numbers sorted. Therefore we have a sorting mechanism. If we are given some number, it will not be difficult to get them sorted. This is a new sorting algorithm for you. It is very simple. Just make BST with these numbers and run the inorder traversal. The numbers obtained from the inorder traversal are sorted.

In the inorder method, we do not print the value of node first. We go to traverse its left subtree. When we come back from the left subtree and print the value of this node. Afterwards, we go to the right subtree. Now consider the above tree of figure 13.4. If we start from number 14, it will not be printed. Then we will go to the left subtree. The left subtree is itself a tree. The number 4 is its root. Now being at the node 4, we again look if there is any left subtree of this node. If it has a left subtree, we will not print 4 and call the inorder method on its left subtree. As there is a left subtree of 4 that consists a single node i.e. 3, we go to that node. Now we call the inorder of node 3 to see if there is a subtree of it. As there is no left subtree of 3, the if statement that checks if the node is not NULL will become false. Here the recursive calls will not be executed. We will come back from the call and print the number 3. Thus the first number that is printed in the inorder traversal is 3. After printing 3, we go to its right subtree that is also NULL. So we come back to node 3. Now as we have traversed the left and right subtrees of 3 which itself is a left subtree of 4, thus we have traversed the left subtree of 4. Now we print the value 4 and go to the right subtree of 4. We come at node 9. Before printing 9 we go to its left subtree that leads us to node 7. In this subtree with root 7, we will not print 7. Now we will go to its left subtree which is node 5. We look for the left subtree of 5 which is NULL. Now we print the value 5. Thus, we have so far printed the numbers 3, 4 and 5. Now we come back to 7. After traversing its left subtree, we print the number 7. The right subtree of 7 is NULL. Thus finally, we have traversed the whole tree whose root is 7. It is a left subtree of 9. Now, we will come back to 9 and print it (as its left subtree has been traversed). The right subtree of 9 is NULL. So there is no need to traverse it. Thus the whole tree having 9 as its root has been traversed. So we come back to the root 4, the right subtree of which is the tree with root 9. Resultantly, the left and right subtree of 4 have been traversed now. Thus we have printed the numbers 3, 4, 5, 7 and 9. Now from here (i.e. node 4) we go to the node 14 whose left subtree has been traversed. Now we print 14 and go to its right subtree. The right subtree of 14 has 15 as the root. From here, we repeat the same process earlier carried out in case of the left subtree of 14. As a result of this process, the numbers 15, 16, 17, 18 and 20 are printed. Thus we get the numbers stored in the tree in a sorted order. And we get the numbers printed as 3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20. This sorted order is only in the inorder traversal.

When we apply the post order traversal on the same tree, the numbers we get are not in sorted order. The numbers got through postorder traversal are in the following order:

3 5 7 9 4 17 16 20 18 15 14

We see that these are not in a sorted order. In order to delete the node from BST, click here.

Technorati Tags: ds tutorial,data structure tutorial,tree data structure,trees in data structure,tree ds,tree traversal data structure,tree types,types of trees,binary trees,binary search trees,bst,bst data structure,bst ds,complete binary search tree,non tree structure,linear tree,binary search tree