The travino function is a recursive function. First, it ensures the supplied node is not NULL. If the node is not NULL, a recursive call to the travino function is made with the node's left child. The node is checked to ensure it's not NULL. If it isn't, again, a recursive call to the travino function is made with its left child. If the node is NULL, the value in the data member of the node is displayed on the screen and a recursive call to the travino function is made with the node's right child. This procedure is repeated until all of the nodes that are displayed on the screen have been visited.
The inorder traversal is described as L,V,R, as follows:
- L means visiting the left child
- V means visiting the node that is displaying its content
- R means visiting the right child
On each node of the binary tree, LVR operations are applied, beginning from the root node. Our binary tree has already been created and looks as follows. At node 40, three operations—L,V, and R—are applied. L means visiting its left child, so we move to the left child of node 40, but two of its operations, V and R, still need to be completed on the node left. So, node 40 is pushed onto the stack with V and R attached to it:
The left child of node 40 is node 20. Again, at node 20, three operations—L,V, and R—are applied. First, L (the left child) is visited. Only two operations, V and R, are left. So, again, node 20 is pushed onto the stack with V and R attached to it. The left child of node 20 is node 10. Again, at this node L, V, and R are applied. Since its left child is NULL, the second operation, V, is applied; that is, the node is displayed or we can say it is traversed. After that, we go to its right child. The right child of node 10 is NULL and since all three operations (L,V, and R) have been applied on this node, it is not pushed to the stack:
Now, node 20 is popped from the stack. Its two operations, V and R, are pending. First, it is visited (displayed) and then we go to its right child:
The right child of node 20 is 30. Again, at node 30, three operations—L,V, and R—are applied. First L (the left child) is visited. Since it has no left child, the second operation, V, is applied; that is, node 30 is visited (displayed), and then we go to its right child. It has no right child either and since all three operations (L,V, and R) have been applied on this node, 30 is not pushed to the stack:
Now, node 40 is popped from the stack. Its two operations, V and R, are pending. First, it is visited (displayed) and then we go to its right child. The right child of node 40 is node 60. At node 60, the three operations—L,V, and R—are applied. First, L (the left child) is visited. V and R are left. Here, node 60 is pushed to the stack with V and R attached to it:
The left child of node 60 is node 50. Again at this node, L, V, and R are applied. Since its left child is NULL, the second operation, V, is applied; that is, node 50 is displayed or we can say it is traversed. After that, we go to its right child. The right child of node 50 is NULL and since all three operations (L,V, and R) have been applied to this node, it is not pushed to the stack:
Now, node 60 is popped from the stack. Its two operations, V and R, are pending. First, it is visited (displayed) and then we go to its right child. So, the visited nodes will be 10, 20, 30, 40, 50, and 60.
The right child of node 60 is 80. Again, at node 80, three operations—L,V, and R—are applied. First, L (its left child) is visited. Since it has no left child, the second operation, V, is applied; that is, node 80 is visited (displayed), and then we go to its right child. It has no right child either and since all three operations (L,V, and R) have been applied to this node, 80 is not pushed to the stack.
So, the final inorder traversal of the tree is 10, 20, 30, 40, 50, 60, and 80.
The program is compiled using the GCC compiler using the following statement:
D:\CAdvBook>GCC binarysearchtree.c - binarysearchtree
As shown in the following screenshot, no error appears when we compile. This means the binarysearchtree.c program has successfully compiled into a .exe file called binarysearchtree.exe. Let's run the executable file and enter some elements to create a binary tree and see its inorder traversal. By doing this, we get the following output:
