This query has been in my mind for many days and I wanted someone to clear it. Problem:- Find the number of nodes in a binary tree
Approach 1 :- (Iterative) Do Inorder traversal using the stack. whenever you are popping elements from the stack, keep a count of it which are number of nodes in a binary tree.
Time Complexity - O(n)
Space Complexity - O(n)
Approach 2 :- (Recursive)
Time Complexity - O(n)
Space Complexity - O(1) or O(n)????
We can do inorder traversal recursively, but in an interview, which approach would be optimal expressing to the interviewer.....Iterative or recursive?? and also should i consider the recursive call stack space which boils down the space complexity to O(n) or should i stick with the O(1) Space complexity?
Your question - "which approach would be optimal expressing to the interviewer" - can't really be answered by anyone except the interviewer themself. However, the differences between the possible approaches to this problem are worthy of discussion.
For a start, let's note that both the iterative and recursive approaches use a stack; the iterative approach has an explicit stack, but a recursive function works using a call stack which is not managed by the programmer. Therefore the auxiliary space used by either approach will be asymptotically the same, but with a lower constant for the iterative approach since it only pushes nodes to the stack, while the recursive approach pushes whole call frames, including all local variables.
Note that the auxiliary space is O(h) where h is the height of the tree, not O(n) where n is the number of nodes. This is important because the worst case will depend on whether or not the tree is balanced. For an unbalanced tree, the height h is O(n) in the worst case, whereas for a balanced tree, h is O(log n). The question doesn't specify that the tree is balanced, so there is a risk that the recursive approach will overflow the stack when the height of the tree is too large. In contrast, the iterative approach stores an explicit stack in main memory.
That's all a discussion of efficiency, but there is more to programming than algorithmic efficiency. For instance, if the tree is never going to be very large, you might prefer the recursive approach since it is much simpler to write; it takes only a few lines of very clean code. The imperative approach needs to create a stack, and push and pop from it in a loop, so the code is likely to be longer and harder to understand. Don't underestimate the value of clean, easy-to-understand code.
The other thing is that you have jumped straight to in-order traversal as the solution to the problem, but if the problem is to count the number of nodes in a binary tree, then you can traverse it in any order. Pre-order traversal is a bit simpler to implement iteratively than in-order traversal, and is just as efficient.
Alternatively, if the data structure itself can be modified, then it is straightforward to give each node a property holding the cardinality of its subtree. The insert, delete and rebalance operations will need to be modified to maintain this property, but the extra work is O(1), and it allows the size of the tree to be computed in O(1) by simply reading the root node's cardinality property. Adding this property has other benefits, such as supporting a "find the kth node" operation in O(h) time instead of O(h + k).