RunTime Complexity of Recursive BinaryTree Traversal

Question

This is my solution to the problem, where, given a Binary Tree, you're asked to find, the total sum of all non-directly linked nodes. "Directly linked" refers to parent-child relationship, just to be clear.

My solution If the current node is visited, you're not allowed to visit the nodes at the next level. If the current node, however, is not visited, you may or may not visit the nodes at the next level.

It passes all tests. However, what is the run time complexity of this Recursive Binary Tree Traversal. I think it's 2^n because, at every node, you have two choices, whether to use it, or not use it, and accordingly, the next level, would have two choices for each of these choices and so on.

Space complexity : Not using any additional space for storage, but since this is a recursive implementation, stack space is used, and the maximum elements in the stack, could be the height of the tree, which is n. so O(n) ?

public int rob(TreeNode root) {
        return rob(root, false);
    }

    public int rob(TreeNode root, boolean previousStateUsed) {

        if(root == null)
            return 0;

        if(root.left == null && root.right == null)
        {
            if(previousStateUsed == true)
                return 0;
            return root.val;
        }

        if(previousStateUsed == true)
        {
            int leftSumIfCurrentIsNotUsedNotUsed = rob(root.left, false);
            int rightSumIfCurrentIsNotUsed = rob(root.right, false);
            return leftSumIfCurrentIsNotUsedNotUsed + rightSumIfCurrentIsNotUsed;
        }
        else
        {
            int leftSumIfCurrentIsNotUsedNotUsed = rob(root.left, false);
            int rightSumIfCurrentIsNotUsed = rob(root.right, false);
            int leftSumIsCurrentIsUsed = rob(root.left, true); 
            int rightSumIfCurrentIsUsed = rob(root.right, true);
            return Math.max(leftSumIfCurrentIsNotUsedNotUsed + rightSumIfCurrentIsNotUsed, leftSumIsCurrentIsUsed + rightSumIfCurrentIsUsed + root.val);
        }

    }

ryan ryan · Accepted Answer · 2017-06-25T01:46:52

Your current recursive solution would be O(2^n). It's pretty clear to see if we take an example:

Next, let's cross out alternating layers of nodes:

With the remaining nodes we have about n/2 nodes (this will vary, but you can always remove alternating layers to get at least n/2 - 1 nodes worst case). With just these nodes, we can make any combination of them because none of them are conflicting. Therefore we can be certain that this takes at least Omega( 2^(n/2) ) time worst case. You can probably get a tighter bound, but this should make you realize your solution will not scale well.

This problem is a pretty common adaptation of the Max Non-Adajacent Sum Problem.

You should be able to use dynamic programming on this. I would highly recommend it. Imagine we are finding the solution for node i. Let's assume we already have the solution to nodes i.left and i.right and let's also assume we have the solution to their children (i's grandchildren). We now have 2 options for i's max solution:

max-sum(i.left) + max-sum(i.right)
i.val + max-sum(i.left.left) + max-sum(i.left.right) + max-sum(i.right.left) + max-sum(i.right.right)

You take the max of these and that's your solution for i. You can perform this bottom-up DP or use memoization in your current program. Either should work. The best part is, now your solution is O(n)!

RunTime Complexity of Recursive BinaryTree Traversal

1 Answers