CODEWITHSUNDEEP
javarecursiontime-complexitydepth-first-search
KKKK
KKKK

Reputation: 347

Recursion vs Depth first search

I have a binary search tree and I want to find the minimum path sum from root to leaf, below is my recursion solution

public int Solution(TreeNode root) {
    if (root == null)   return 0;
    if (root.left != null && root.right == null)
        return Solution(root.left) + root.val;
    if (root.left == null && root.right != null)
        return Solution(root.right) + root.val;
    return Math.min(Solution(root.left), Solution(root.right)) + root.val;
}

Question #1:

Is this solution Depth First Search because it first goes through to the deepest place of the left subtree (I assume).

Question #2:

What is the time complexity and space complexity of this method?

Upvotes: 0

Views: 277

Answers (1)

Jan
Jan

Reputation: 1504

First of all, this question would have been better in codeReview or computer science . Not sure which, but I would tend to use computer science for complexity questions.

Nevertheless:

Answer 1:

Yes it is indeed depth first, because you reach the leaves in the left subtree before even starting with the right subtree.

Answer 2:

Since you only evaluate each Node exactly once, your time complexity is O(n) where n is the number of Nodes in your tree.

Your Space complexity should be something like O(d) where d is the depth of the tree, since you have to remeber Solution(left) when calculating Solution(right)

Upvotes: 1

Related Questions