Find time and space complextity of the following code. public class MaxPathSumBi

Question

Find time and space complextity of the following code.

public class MaxPathSumBinaryTree {

   public int maxPathSum(TreeNode root) {

       //wrap a global variable into an array so that we can change the value//

       int[] max = new int[] {Integer.MIN_VALUE};

       maxSumHelper(root, max);

       return max[0];

   }

   private int maxSumHelper(TreeNode root, int[] max) {

       if (root == null) {

           return 0;

       }

       int left = maxSumHelper(root.left, max);

       int right = maxSumHelper(root.right, max);

       //when root node has both left and right child, we need to update the max path sum//

       if (root.left != null && root.right != null) {

           max[0] = Math.max(max[0], left + right + root.key);

           return Math.max(left, right) +root.key;

       }

       return root.left == null?right + root.key : left + root.key;

   }

}

Explanation / Answer

maxPathSum will call a function maxSumHelper

maxSumHelper:
left = maxSumHelper(r. left) this will make a call to left subtree
right = maxSumHelper(r. right) this will make a call to right subtree ,

When the appropriate values are return we compute the maximum of the values between left and right etc

So all in all, we will be iterating till all the Nodes in the tree and nopt more than That.
Suppose we have N nodes in Tree, So Time Complexity will be O(N) because we will iterate max to max , total nodes in the tree


Space complexity: The depth of the recursion will be O(N) , So the Space complexity is O(N)


Thanks, let me know if there is any concern/doubts.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.