In this case traverseInOrder use Recursive Approach. We can reduce the time complexity and the space complexity by using Stack.

Recursive Approach

Complexity Analysis

• Time complexity : O(n). The time complexity is O(n) because the recursive function is T(n)=2⋅T(n/2)+1.
• Space complexity : The worst case space required is O(n), and in the average case it's O(logn) where n is number of nodes.

Iterating method using Stack

Complexity Analysis

• Time complexity : O(n).
• Space complexity : O(n).