In-order traversal is one of the standard depth-first traversals for binary trees. The order of visiting nodes in an in-order traversal is: Left subtree $ ightarrow$ Root $ ightarrow$ Right subtree.
Recursive Implementation
We use a recursive helper method. The helper traverses the left subtree, records the current node's data value, and then traverses the right subtree. If a node is null, the function hits its base case and returns.
class Solution {
ArrayList result = new ArrayList<>();
// Function to return a list containing the inorder traversal of the tree.
ArrayList inOrder(Node root) {
inOrderHelper(root);
return result;
}
private void inOrderHelper( Node root ){
if( root == null ) return;
inOrderHelper( root.left );
result.add(root.data);
inOrderHelper( root.right );
}
}
Complexity Analysis
- Time Complexity: $O(N)$ where $N$ is the number of nodes in the binary tree. Every node is visited exactly once.
- Space Complexity: $O(H)$ auxiliary space where $H$ is the height of the tree. This space represents the call stack depth during recursion. In the worst case (skewed tree), $H = N$.