Tree Problems - Understanding when to implement iterative solution v.s. when to implement recursive solution

user_13742194 0
Viewed 300

I've been working on algorithm problems in my free time as a way to prep for interviews for summer internships next summer. I'm currently working on tree problems, and I've found that the actual coding is pretty trivial for most problems, but I have a hard time understanding the complexity of these problems. A problem I was working on is Binary tree Preorder Traversal, and I implemented it both recursively and iteratively. However, the iterative solution was much slower, and I don't understand why? here are my two solutions:

Iterative:

public List<Integer> preorder(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();

    if (root == null) return ans;

    stack.push(root);

    while(!stack.isEmpty()) {
        TreeNode node = stack.pop();
        ans.add(node.val);

        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    {

    return ans;
}

Recursive:

public list<Integer> preorder(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    dfs(root, ans);
    return ans;
}

public void dfs (TreeNode root, List<Integer> ans) {
    if (root == null) return;
    ans.add(root.val);
    dfs(root.left);
    dfs(node.right)
}

As far as I can see, the recursive solution has two branches per call, and the depth of the tree if balanced is O(log n), however worst case is O(n), so the complexity would be O(2^n). I could be completely off and probably am. The iterative solution has constant push and pop time, so my initial intuition was that it would be O(n) time. If these were the circumstances, I can't see how the exponential solution would run faster. If somebody could help me understand the complexities of such problems that would be greatly appreciated.

recursion iteration time-complexity algorithm java
2 Answers

Time complexity is O(n) in both cases: you visit each node once and do constant amount of work per node (adding value to ArrayList or Stack is amortized O(1)).

One of the reasons why your iterative solution is slower might be usage of Stack. This class is synchronized (it extends Vector). You don't need thread-safety in this case, so consider replacing it with ArrayDeque: 

Deque<Integer> stack = new ArrayDeque<Integer>();

Space complexity is also O(n) in both cases: explicit stack in the iterative solution and implicit call stack in the recursive solution can grow to n (unbalanced case).

user_42686630

Something having constant complexity vs exponential does not mean it's faster. It just says something about the rate it will get slower as your input grows. I'd say that this is a pretty valuable lesson in itself for interviews and the real world, as the solution with the lowest O-time often isn't the 'best' or more practical.

Aside from the complexity though, I can see that the stack-based approach could just be slower just because it needs to pop and push items on the stack, whereas the recursive solution only needs to call a function. I can't say this with certainty without doing a benchmark.

user_809110
Related