Given a binary tree, write iterative and recursive solution to traverse the tree using in-order traversal in C++ and Java.
Unlike linked lists, one-dimensional arrays and other linear data structures, which are traversed in linear order, trees may be traversed in multiple ways in depth-first order (pre-order, in-order, and post-order) or breadth-first order (level order traversal). Beyond these basic traversals, various more complex or hybrid schemes are possible, such as depth-limited searches like iterative deepening depth-first search. In this post, inorder tree traversal is discussed in detail.
Traversing a tree involves iterating over all nodes in some manner. As tree is not a linear data structure, from a given node there can be more than one possible next node, so some nodes must be deferred i.e stored in some way for later visiting. The traversal can be done iteratively where the deferred nodes are stored in the stack or it can be done by recursion where the deferred nodes are stored implicitly in the call stack.
For traversing a (non-empty) binary tree in in-order fashion, we must do these three things for every node N starting from root node of the tree:
(N) Process N itself
(R) Recursively traverse its right subtree. When this step is finished we are back at N again.
In normal in-order traversal we visit left subtree before the right subtree. If we visit right subtree before visiting the left subtree, it is referred as reverse in-order traversal.
As we can see before processing any node, the left subtree is processed first, followed by the node and the right subtree is processed at last. These operations can be defined recursively for each node. The recursive implementation is referred to as depth-first search (DFS), as the search tree is deepened as much as possible on each child before going to the next sibling.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Recursive function to perform in-order traversal of the tree void inorder(Node *root) { // return if the current node is empty if (root == nullptr) return; // Traverse the left subtree inorder(root->left); // Display the data part of the root (or current node) cout << root->data << " "; // Traverse the right subtree inorder(root->right); } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Recursive function to perform in-order traversal of the tree public static void inorder(TreeNode root) { // return if the current node is empty if (root == null) { return; } // Traverse the left subtree inorder(root.left); // Display the data part of the root (or current node) System.out.print(root.data + " "); // Traverse the right subtree inorder(root.right); } |
Iterative implementation –
To convert above recursive procedure to iterative one, we need an explicit stack. Below is a simple stack based iterative algorithm to do in-order traversal.
iterativeInorder(node)
s -> empty stack
while (not s.isEmpty() or node -> null)
if (node -> null)
s.push(node)
node -> node.left
else
node -> s.pop()
visit(node)
node -> node.right
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
// Iterative function to perform in-order traversal of the tree void inorderIterative(Node *root) { // create an empty stack stack<Node*> stack; // start from root node (set current node to root node) Node *curr = root; // if current node is null and stack is also empty, we're done while (!stack.empty() || curr != nullptr) { // if current node is not null, push it to the stack (defer it) // and move to its left child if (curr != nullptr) { stack.push(curr); curr = curr->left; } else { // else if current node is null, we pop an element from stack, // print it and finally set current node to its right child curr = stack.top(); stack.pop(); cout << curr->data << " "; curr = curr->right; } } } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
// Iterative function to perform in-order traversal of the tree public static void inorderIterative(TreeNode root) { // create an empty stack Stack<TreeNode> stack = new Stack(); // start from root node (set current node to root node) TreeNode curr = root; // if current node is null and stack is also empty, we're done while (!stack.empty() || curr != null) { // if current node is not null, push it to the stack (defer it) // and move to its left child if (curr != null) { stack.push(curr); curr = curr.left; } else { // else if current node is null, we pop an element from stack, // print it and finally set current node to its right child curr = stack.pop(); System.out.print(curr.data + " "); curr = curr.right; } } } |
The time complexity of above solutions is O(n) and space complexity of the program is O(n) as space required is proportional to the height of the tree which can be equal to number of nodes in the tree in worst case for skewed trees.
References: https://en.wikipedia.org/wiki/Tree_traversal
(1 votes, average: 5.00 out of 5)
Loading...
Thanks for reading.
Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply
Inorder traversing should give sorted nodes!!
Thanks for sharing your concerns. Inorder traversing gives sorted nodes only when the given binary tree is a BST.