Tree: Inorder Traversal is a coding challenge with easy difficulty in the HackerRank data structures category. In this blog post, we’ll discuss how we can solve it in JavaScript in O(n) time and O(1) space.
Problem Statement
In this challenge, you are required to implement inorder traversal of a tree.
Complete the inOrder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree’s inorder traversal as a single line of space-separated values.
Read full details and access the challenge on Tree: Inorder Traversal | HackerRank
Solution
function inOrder(root) {
if (root) {
inOrder(root.left);
process.stdout.write(root.data + ' ');
inOrder(root.right);
}
}
Time Complexity : O(n)
Space Complexity : O(1)
In this challenge, we have to print out all the nodes from the tree in an ascending order. Since tree is already structured in an ordered way (smaller nodes to the left and larger nodes to the right), we just have to use recursion like the code above to print the small nodes first, then the large nodes.
We’re visiting all the nodes and use no extra data structure so we have O(n) time and O(1) space complexity.
Conclusion
That’s how you can solve the Tree: Inorder Traversal Challenge in HackerRank.
This is a basic skill on trees and it is a nice challenge to improve our knowledge.
If you have another approach different from mine, please do comment below!
Check out the rest of my blog for more helpful contents on Data Structures and Algorithms in JavaScript! We’ll also discuss more HackerRank solutions in JavaScript for the upcoming posts!
See you next post!