Exploring Tree-Inorder Traversal
In last post Introduction to tree data structures, I have give a brief introduction about tree data structure and its applications. Traversing a tree data structure is interesting as well as complicated as compare to linear data structures. Unlike arrays or linked list which are traversed in linear order, tree data structure can we traversed in multiple ways like depth first order (inorder, preorder, postorder) and breadth first order(level order traversal).In this article we will discuss inorder traversal using two approaches the iterative way and recursive way.
Each node of the tress needs to be visited in some specific way while traversing a tree. Unlike linear data structure , there can be more than one possible next node from a given root node because of the some nodes must be skipped i.e. stored in some way so that it can be visited later. The traversing can be done iteratively where the stored skipped node is stored in a stack or it can also be done by recursion, where the skipped node is stored implicitly in a call stack.
While traversing a non-empty binary tree in an inorder way, three things need to be done for every “n” node starting from the tree root.
1. Traverse the left subtree and print the node value. when this step is finished return back to “n” node.
2. Print the “n” node value
3. Traverse the right subtree and print the node value. when this step is finished return back to “n” node
Let us first discuss the iterative approach along with the code.
1. Iterative method-
The left subtree needs to processed first before processing any other node followed by the root node and at last the right node or right subtree. In the iterative approach we will use an explicit stack to perform inorder traversal. Below is the code:-
We will create a empty stack to hold the skipped node. We will start from the root and set the current node to root node. If the current node is none and stack is empty ,we will exit the while loop. Inside the while loop we will check if the current node is present , we will push the current node to the stack and we will skip the current node and move to the left node. After moving to the left node if the current node is none , we will pop the node from the stack and place it in current node. We will append the current node value in the list inorder and then move to the right node of the current. At last we will return the inorder list which holds all the traversed value of the tree
2. Recursive method-
Similar to the iterative approach we will first visit the left subtree then the root node and at last the right subtree. This operation are done recursively on each node
We will star from the root node, if the root node is empty we will return a empty list. Similar to iterative approach we will first visit the left subtree , recursion will place the skipped node in implicitly in a call stack . It will append the left node values in element list and then return back to the root node , the root node value is stored in the element list. Once the left node value becomes none , we will move to right node and perform the same operation and place the values of right node in element list. At last we will return the element list which hold all the traversed values of the tree.
Time and space complexities-
The time complexity of the above code is O(n),where n is total number of node in a binary tree. The space complexity of the code is O(n) as space required a directly proportional to the height of the tree which in case can be equal to the total number of nodes in the trees in worst case for skewed trees.
Conclusion-
Traversing in simple words means exploring, we all are in journey of life. But this journey is not about the end its about experiences and challenges. My only message to readers is enjoy the journey ,keep learning and never ever give up. At the end everything works out for the best…..(cheers-PN)
