Let's now discuss the space and time complexity of the approach that we have discussed for solving path
sum two.
The space complexity of the solution that we came up with is of the order of H, where h is the maximum
height of the binary tree.
Now why is this the case?
Let's try to think about that.
Let's say the binary tree which is given to us has this structure.
Now for the approach that we came up with.
What are the things that take up auxiliary space or extra space?
The things that take up extra space are the Cur array.
And we will also be using space on the recursive call stack.
Now notice over here in this path where we go from the root to the leaf, this is the case where cur
would have the maximum number of values which is four okay.
And in this case the recursive call stack will also take up space of the order of H, where h is the
maximum height of the binary tree.
So that's why we can say that the space complexity of this solution is of the order of H.
Now notice that in the worst case, the space complexity will be of the order of n.
Now why is that the case?
Let's take another example to understand that.
Now if the binary tree which is given to us is a skewed binary tree and it looks like this over here,
notice that Cur would take up space of the order of n, and the space taken up on the recursive call
stack will also be of the order of n.
So that's why the worst case space complexity of this solution is of the order of n.
Now, when it comes to their time complexity, the time complexity of this solution is of the order
of n into h, where n is the number of nodes in the given binary tree, and h is the maximum height
of the given binary tree.
Now let's try to understand why this is the case.
For this.
Let's take an example where the binary tree which is given to us is a perfectly full binary tree.
Now, if you have a perfectly full binary tree, and if this tree over here has n nodes, the number
of leaf nodes this tree has will be approximately n divided by two.
Now let's quickly take a side note to understand why this is the case.
Okay, now in a perfectly full binary tree, if h is the height of the binary tree, then the number
of nodes in that binary tree will be two to the power h plus one minus one.
Now over here notice that h is equal to two okay and two to the power.
Two plus one will be two to the power three minus one two to the power three minus one is eight minus
one which is seven.
And notice over here in this perfectly full binary tree where height is equal to two, there are indeed
seven nodes.
Now over here we have four leaf nodes.
And to get the number of leaf nodes we'll just have to do two to the power h which is two to the power
two over here.
And that's equal to four.
Now when we do four divided by seven that's approximately half of the nodes okay.
Or over here.
Also you can think of it in this manner two to the power H divided by two to the power H plus one minus
one is approximately half okay.
And if it was just two to the power h divided by two to the power h plus one, it would have been exactly
half.
Now we are saying approximately half because over here we have a minus one.
All right.
So we have discussed that in a perfectly full binary tree there are approximately n by two leaf nodes.
Now let's use this to come up with the time complexity for the approach that we discussed in the approach
video, we have seen that we have to visit every root to leaf path, because the nodes can have positive
as well as negative values.
So we have to visit every node.
And because there are n nodes visiting every node will need work of the order of n.
Now in these n by two cases where we are at leaf nodes, we potentially need to do O of H operations,
because if the values of the nodes starting at the root node till that particular leaf node adds up
to the target sum, then we would have to make a copy of that particular cur and append it to the results
array.
And making a copy of cur is an operation which takes up work of the order of the size of the current
array.
And because h is the height of the binary tree, the number of elements in cur will be of the order
of H.
So that's why in the n by two leaf node cases, we potentially may need to do o of h operations.
So we need to do O of N operations to visit every node.
And if I divide this n into n by two.
And n by two.
Where these n by two represents leaf nodes and these are the other nodes.
We have seen that in the case of the leaf nodes we may have to do O of H operations.
And in the other cases we are just doing constant time operations.
So that's why the time complexity of this approach is of the order of n by two into one plus n by two
into h.
And this over here simplifies to n into h.
So that's why the time complexity of the approach that we came up with is of the order of n into h.
Now let's make some space over here.
Now in the worst case scenario.
And that would be the case where we are given a skewed binary tree.
The height of the binary tree can be of the order of n, right.
And that's why the worst case time complexity of this solution is of the order of n into n.
Okay.
And again, a skewed binary tree is something that looks like this.
And notice over here the height is equal to n itself okay.
So that's why the worst case time complexity of the solution that we came up with is of the order of
n square.