Curious about Inorder Traversal of a Binary Tree?

Let's dive in!

It's a technique for traversing all nodes of a tree. In a binary tree, we traverse the left subtree, then the current node, and finally the right subtree.

What is Inorder Traversal?

Are you wondering how inorder traversal applies to n-ary trees? Due to the lack of left or right children, these techniques are most effective in binary trees.

Inorder Traversal With Recursion

Want to try inorder traversal with recursion? The flow goes left subtree, current node, and right subtree. Don't forget to check if the node is present before traversing.

Algorithm-    1. Traverse left child with a recursive call passing current->left as root.  2. After returning from call, the node would be leftmost so that we can store this as first node of inorder traversal.

Time complexity: O(N), where N is no of nodes in tree.  Space complexity: O(1)

Want to try a different approach? Inorder traversal can also be done iteratively using a stack data structure.

Inorder Traversal Iterative

Algorithm-   1. Create a stack to store the values while traversing to leftmost child.  2. Create a current node as root.

Time complexity: O(N), where N is no of nodes in the tree.  Space complexity: O(N).

Want to know a neat trick? When doing inorder traversal on a binary search tree, you'll find the result is always in sorted order. Why is that?