Welcome back.
Let's now take a look at the time and space complexity for the iterative approach for implementing preorder
traversal on a binary tree.
Now, when it comes to the time complexity, this approach is going to be having a time complexity of
the order of n, where n is the number of nodes in the given binary tree, because we will be visiting
every node one time.
What about the space complexity?
The space complexity of this solution is going to be of the order of H, where h is the maximum height
of the tree.
Now why is that the case?
Notice that in the worst case, for each level that we go down in the binary tree, we will be popping
one node from the stack and we will be adding two nodes.
The left and right child of the node that was popped to the stack.
So net net we are going to remove one node and add two nodes.
So that's adding one node.
So for every level that we go down in the binary tree, in the worst case we will be adding one node
to the stack.
So that's why the space complexity or the maximum auxiliary space that will be used at any given point
of time, will be of the order of H, where H is the maximum height of the binary tree.