educative.io

I am missing something

Courses
,
#1

Trying to understand the time and space complexity of this algorithm the explanation says that we have O(2^N) leaf nodes and me looking at the diagram doesn’t really add up.

The example is for N= 3 and which would mean 8 leaf nodes but in reality we only have 5.

Could someone please clear this out for me.

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5753264117121024

#2

Hi @Demos

The explanation says that we will have 2^n leaf nodes if we don’t care for the ordering of the parentheses. This means that, if we were not restricted to placing a close parenthesis ) only after an open parenthesis (, we would have a total of 2^n combinations. The actual number of combinations is less than 2^n due to the rules we have imposed.

Hope this helped!

#3

Hi,
I have a question about this part, too. Why do we have 2^N - 1 intermediate nodes? What do we mean by intermediate here?