Count Total Unique Binary Search Trees - The nth Catalan Number (Dynamic Programming)

Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?
Catalan Numbers: en.wikipedia.org/wiki/Catalan...
Define G(n): the number of unique BST for a sequence of length n.
G(0) = 1
G(1) = 1
For each element, we can place it and recurse on the left an right not including that number we choose to root that subtree.
Define F(i,n): the number of unique BST, where the number i is served as the root of BST (1 is less than or equal to i which is less than or equal to n).
G(n) = the summation from 1 to n of F(i, n)
When we choose an element to root a subtree from the possible elements to root there, we split the possibilities into a left and a right of the original enumeration.
Example:
n = 5 aka [1, 2, 3, 4, 5]
When evaluating F(3, 5) we will have
a left subtree with [1, 2] aka G(2)
a right subtree with [4, 5] aka G(2)
G(n) evaluates the # of unique trees we can construct from a total of n possible values, regardless of what those values are.
The Realization
We notice that F(i, n) = G(i - 1) * G(n - i)
To get F(i, n) we are considering all combinations of left tree possibilities with all of the right tree possibilities.
These exhaustive pairings between two sets of items is called a cartesian product.
Now we have a new way to express F(i, n)
F(i, n) = G(i - 1) * G(n - i)
G(n) = summation from 1 to n of G(i - 1) * G(n - i)
This now can be solved with DP via top-down recursion or bottom up.
For each G(n) up to our requested n we will solve the G(n) summation equation.
At the end we return the G(n) requested which by the end we will have an answer for.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech

[@BackToBackSWE]

Table of Contents: The Problem Introduction 0:00 - 1:11 The Placement Intuition 1:11 - 6:56 Introduction To The Transition To Formal Equations 6:56 - 7:18 The Definition For G(n) 7:18 - 7:50 The Definition For F(i, n) 7:50 - 8:44 Applying Our Definitions To Our Previous Intuitions 8:44 - 10:43 The Final Mental Leap: The Cartesian Product 10:43 - 12:44 Time Complexity 12:44 - 13:20 Space Complexity 13:20 - 13:44 The Wrap Up 13:44 - 13:59 Mistakes: 7:18 -> G(n) actually represents the amount of structurally unique BST's we can construct given n nodes. It does not have to be nodes valued from 1...n because values won't matter as long as they are in sequence. (so G(3) can represent 3, 4, 5 or 1, 2, 3 or .... and so on). This is true because the way our possibilities pan out will be the same for the 3 nodes 3, 4, 5 and the 3 nodes 1, 2, 3. The code for this problem is in the description. Fully commented for understanding and teaching purposes.

[@AhmedAli-jx9ie]

can you write in the video description the online judge problems related to the explanation videos like here is a tutorial about binary tree, go solve these problems to practice what you just learned that's will be more helpful thanks in advance

[@BackToBackSWE]

Yes we will be implementing this on backtobackswe.com (paywall) soon, we won't go back to the KZbin and do this

[@florencechan8863]

I didn't understand the explanation for the multiplication at first. Maybe it's just me but I don't feel like its well explained -- cross sections doesn't visually tell me anything. So for those who are asking to yourselves, why multiply? Let's take a step back: What is G(1), G(2), G(3), ... G(n) etc. It describes a binary search tree with n nodes (doesn't matter what the root is) and the value it represents is the number of structurally unique binary search trees we could make given n nodes. So let's say we have G(3) 1 3. 2 1 3 2 2 1 3 3 1 3. 1 2 2 Those are the 5 trees. So if we have for example f(3,6) this expands to something like below: f(3,6) / \ G(2) G(3) G(2) looks like this 2. 1 1. 2 So 2 trees Why is it multiplication? Well, let's stop thinking about trees and the tree structure and take a step back further If I give you two arrays and I want to know the number of possible values you can make (doesn't matter if there's repetition) by taking one number from one array and one letter from the second. For example: A B 1 2 3 4 5 Your mind will likely naturally match it up like this: A / / | \ \ 1 2 3 4 5 B / / | \ \ 1 2 3 4 5 Kinda hard to draw with a keyboard, but my point is you will do something like Fix the Letter and match it with every single possible number. So A1 A2 A3 A4 A5 then B1 B2 B3 B4 B5. Now the number we get is 10, which is actually just 2 * 5. If you see the pattern your brain automatically dead when matching it up it said, fix 1 letter for each letter and match it to each number. For every letter we match to N numbers -- and we do this M times --> N is the size of the number array and M is the size of the letter array. So N*M. How is this related to the tree? Same idea but not arrays. You are fixing a root. Not sure if this will work for you but the way it clicked for me was when I visualized the left subtree with a fixed root (any valid fixed root). Then I rotate through all the valid possible right subtree roots. So for one fixed left root, that's rotates whatever number in side G() for the right root. But we do this by the number of valid fixed roots on the left subtree which is also whatever number inside G() for the left root. Now I hope you see why it's multiple. It's just permutation in a slightly wonkier way. Just to be even more clear for f(3,6) in the example I give earlier it'll start out like this: Left subtree possibilities: Remember G(2) = 2 2. 1 1. 2 Right Subtree possibilities Remember G(3) = 5 1 3. 2 1 3 2 2 1 3 3 1 3. 1 2 2 So on the left is 2 match it with 1 on the right 1. 2 3 Fix the two rotate the right to all the possible right tree possibilities. By rotate, I mean use the different right tree possibilities (I may have been unclear on that). So: Left Right 2 3. 1 2 1 Left Right 2 2 1 1 3 Left Right 2 1 1 3 2 Left. Right 2 3 1 1 2 So that's 5 possibilities already. But left can be 1 2 as well, so repeat the whole process with it fixed at 1. That's a total of 10 possibilities. i.e 2*5. Remember G(2) = 2 and G(3) = 5. Well G(2) * G(5) = 10. It's not magic that it all works out at the end. Just a sprinkling of permutation :) I kinda feel dumb for not noticing this at first. It just goes to show that sometimes we have to take a step back and not be so focused on what's in front of us (the tree and tree structure) and think of the bigger picture which is really just a permutation that our brain can naturally handle with arrays.

[@BackToBackSWE]

yeah this was one of my early videos, getting better every video, thanks for this - hope it helps someone reading this

[@vincentkoo4453]

This post helped me a lot, thank you very much

[@BackToBackSWE]

@@vincentkoo4453 nice

[@eug_gino]

this was a beautiful explanation, you should def try to make some leet code tutorials sometime

[@BackToBackSWE]

@@eug_gino I support

[@kevinnguyen9397]

Thanks for this! I was actually doing this problem the other day, and had trouble with the intuition and had to step away. You definitely cleared it up for me.

[@BackToBackSWE]

That is AWESOME. This is what I'm all about. I've had hundreds of those "step away" moments and that is what inspired me to make explanations myself since I felt others didn't explain it the way my brain "taught me" if that makes sense. This is my goal for this channel. Thank you.

[@yousufhussain9530]

Same here. I looked at a few solutions and couldn’t really understand them. Thinking of dividing the solution space as a cloud was a lightbulb moment. Thank you! 🙏

[@ankitgoyal8556]

Hey, u are compelling me not to mug up. The first time I feel like this video is good, the second time I feel like this is out of the world. Thank you so much, brother.

[@BackToBackSWE]

great and tahnks

[@SamM-ne5uq]

You do not give out just solution to the problem but explain how to develop the final solution. It is simply awesome. Thank you!

[@BackToBackSWE]

sure

[@soymaxxing]

Great explanation, I was having trouble visualizing how this problem had an optimal substructure. But ur explanation from how G(n) related to F(i, n) really helped me see it! Thanks

[@BackToBackSWE]

sure

[@yuvrajjagga9351]

I tried for around 3 hours on this problem. It was strange because I could analyse the problem and it's requirement but I could not ,like you said, materialize the logic into a recursive programming solution, only to find out, after watching this video, that it lies in Dynamic programming zone. A great explanatory video.

[@BackToBackSWE]

I did the. same, I didn't get this first time I did it

[@snowy0110]

It's rare to find good explanations. Yours is simple and I appreciate it. Thanks!

[@Oleks380]

Thank you man! You're doing a great job

[@BackToBackSWE]

sure

[@jishulayek8252]

You are an amazing teacher !!! Loved it

[@BackToBackSWE]

thx

[@annettejohn6829]

Thanks a lot! was struggling with the intuition for this and now it makes a lot of sense!

[@jianxiaohu8213]

Thank you, that was so well explained!

[@BackToBackSWE]

sure

[@omnya9381]

Amazing explanation!!! Thank you so much

[@BackToBackSWE]

sure.

[@maripaz5650]

What a beautiful explanation. Thank you! I had a light-bulb moment when you were laying out how to solve n=2 and n=3.

[@BackToBackSWE]

great

[@aynurmukhambetova1708]

i havent even watched it to the end but everything got so clear! thank you

[@BackToBackSWE]

great

[@vivil7917]

Thank you so much for the explanation, very clear and very accurate!

[@chintangotecha7089]

Great explanation. Highly appreciated :)

[@BackToBackSWE]

sure

[@nirankarojha2660]

I love the explanation of the solution. Thanks a lot.

[@BackToBackSWE]

sure

[@waleedahmed1725]

I stumbled onto this video while scratching my head on this problem on leetcode: leetcode.com/problems/unique-binary-search-trees/, and wow I just got to say your explanation was crystal clear and might be one of the most complete I've seen for any leetcode problem that I've gone googling. Glad I stumbled onto your channel!

[@BackToBackSWE]

Thank you. Welcome to the channel.

[@markgraham2312]

It was a good explaination. Thank you.

[@jinhopark3671]

Great explanation. Thanks!

[@OP-yw3ws]

Thanks for the awesome explaination!!!

[@TheGizmoTruck]

year later, this is still helpful. Thank you

[@BackToBackSWE]

dang...it's been a year. sheesh. And sure

[@girishthatte]

Perfect and concise explanation

[@BackToBackSWE]

thanks

[@tumul1474]

I didn't even understand that it was a dp prob but the way u explain it man, I was able to deduce the answer around 9:00...thanks a bunch !!

[@BackToBackSWE]

great to hear

[@Rahul-uk4su]

This was super helpful thanks. I liked the video

[@BackToBackSWE]

great

[@kunqian06]

Thanks for the awesome explanation

[@BackToBackSWE]

sure

[@TheSteak1984]

Big Thank You!

[@kxiong4021]

Thanks for the explanation!!

[@BackToBackSWE]

sure

[@ivantishchenko4686]

Superb explanation!

[@BackToBackSWE]

thx

[@fastisslow6177]

Nice and powerful explanation.

[@gokulgopinath3777]

Great explanation

[@Code4You1]

Thank you bro!

[@sudhakar104624]

Awesome explaination

[@BackToBackSWE]

thx

[@aikolkoikelov7514]

Thanks man for a such clear explanation )

[@BackToBackSWE]

Happy to help!

[@user-oy4kf5wr8l]

Thank u super much man!

[@BackToBackSWE]

ye

[@xxbighotshotxx]

Thank you for this! It was a catalyst for my understanding to this problem. That was fun to derive If there are any of you that was confused as to why F(i,n) = G(i-1) * G(n-i) at 11:00, I suggest drawing out G(5) like he does in this video at 10:39.

[@BackToBackSWE]

hey

[@chris.w391]

Best explanation

[@amitmehta2285]

I love you you helped me really

[@BackToBackSWE]

Thanks buddy! keep hustling

[@rohan8arora]

You're an amazing teacher man. I wonder what's your tech stack in backtobackswe website? Its quite nice.

[@BackToBackSWE]

We are using Next.js rn, but we are rewriting the whole thing and creating a new system that will be out in 3-6 months.

[@user-eg3fq7jp2n]

i comment here so the youtube algorithm will pick this video, amazing video, well explained

[@BackToBackSWE]

thanks

[@motivation_hubPJ]

Thanks a lot bro

[@BackToBackSWE]

sure

[@VijayKumar-bp1fp]

very good explanation...

[@BackToBackSWE]

thanks

[@SidharthJhawar]

Subscribed!!!

[@BackToBackSWE]

hey

[@weibangzhang3994]

great work

[@BackToBackSWE]

thx

[@nithishkumar2561]

Great explanation bro

[@karansagar7870]

Gr8 explanation

[@BackToBackSWE]

thx

[@alirezaRahmanikhalili]

good job

[@BackToBackSWE]

thanks

[@lewisben6697]

If I use vector(ArrayList) instead of an array, it still costs O(n2) time or not?

[@BackToBackSWE]

not sure?

[@punitpawar4231]

Will you be able to put up a video that returns a list of the unique binary trees instead of the count. Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.. Thanks a lot !!

[@BackToBackSWE]

We don't have that yet yes, I think we do have it on backtobackswe.com (paywalled)

[@ZackOfAllTrad3s]

For those still having trouble I would suggest reading the leetcode article after watching this video, they work well together.

[@BackToBackSWE]

yeah

[@Gabriel-ms6qw]

I think a better explanation would be dp[i] are all the ways you can create a binary tree using "i" elements.Lets say you have n = 6, when you root 4, in the left subtree there are only 3 elements less than him so there are dp[3] ways you can arrange those in a binary tree and 2 elements greater than 4 (5,6) so there are only dp[2] ways you can arrange them. Now, For every way you can arrange the left subtree you have dp[2] ways you can arrange the right one, so basically its dp[2] + dp[2] ... + dp[2], this is the multiplication.

[@BackToBackSWE]

Yes, thank you

[@christiansakai]

Hey man, I have a request. On Leetcode there are three templates on Binary Search. It would be great if you do a series of explanation for that!

[@BackToBackSWE]

Very, very, fascinating. I have a video coming out in a 2 or so days (pre-recorded since I'm not in the USA right now) on a binary search problem and I have a code sample for it. It is a Facebook interview question I got first round (I passed 1st round, failed 2nd round although I knew both questions...long story). I approach it with Approach #1 with some tweaks. In my opinion, you only need to know Approach #1 and then every binary search problem will be a tweak of it. I think the whole "templates" concept is a bad idea not because it is not brilliant or well thought out, but because it causes you to MEMORIZE things. And I'm not a fan of that especially for these kinds of questions. (Also a long as the search is truly a binary search, its asymptotic nature will be logarithmic. Some tweaks on approaches will improve wall time but not time complexity) I'm all about intuitions and knowing HOW and WHY a problem is solved a certain way and with binary search, it is all about narrowing search space using a certain set of deductive logic at each step. Anyway, you'll see what I mean when I put that video out. We will do a great amount of binary search this year with many variants.

[@christiansakai]

@@BackToBackSWE Thanks man! I appreciate your time putting videos like these out. It must be a ton of work! Yeah I've been trying to understand the templates thingy to no avail, since there is no explanation on that article on Leetcode. Currently my biggest weaknesses are Binary Search, Backtracking and DP. DP is just so hard to do. I tried various approaches, and like you said, probably I just need to expose myself to more problems on that nature.

[@zzzz26526]

at 8:39 wouldn't the number of nodes you have to work with be 2? if you plant 1, 2 , 3 at the root, do you include the root in the number of nodes you have to work with?

[@jyotisingh8183]

Where is the code in description ?? Thank you for the video.

[@BackToBackSWE]

Hi, the repository is deprecated - we only maintain backtobackswe.com now

[@nishanth998]

your teaching is awesome...!!! plz tell where the code is present...

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com.

[@taiwan.1]

do you have another video that can explain why F(i, n) = G(i-1) * G(n-i) ? any videos for a similar question that may help explain this?

[@BackToBackSWE]

Haha yeah this may not have been enough, I'll recover this question soon

[@taiwan.1]

I got it now.. kinda..... However, Thank you so much for all these videos that you have made. They are all amazing.

[@BackToBackSWE]

@@taiwan.1 No, you have to get it 100%, that's my job. And sure, I dropped the ball here, I'm releasing a course w/ Chris Jereza where I won't let explanations be subpar

[@jayeshmarathe7678]

video on Optimal binary search tree please

[@vedankgoyal1706]

If we use Dynamic Programming our time complexity will be O(n^2) but if we use maths it will become O(1) as the direct formula for Catalan number is 2nCn/n+1. But since it is a programming question DP approach should be known I guess.

[@BackToBackSWE]

ye

[@persianwaffle]

hey vedang, would you mind sharing a link or something where it is being calculated in o(1).

[@vedankgoyal1706]

@@persianwaffle brilliant.org/wiki/catalan-numbers/ We can use the formula for Catalan number

[@RodrigoVillarreal]

The video is fantastic, however I got a bit confused about why do we multiply instead of sum?

[@BackToBackSWE]

thanks! and can you timestamp the part that confuses you (it saves me time because I respond to comments in big batches)

[@harsaroorsohal3867]

since both left and right side are individual and are not related to each other, for each left BST we'd have multiple right BST and vice versa. We need to report the combination of both of them so it's multiplication.

[@heisenberg1844]

Could you please do part 2 of this question, leetcode.com/problems/unique-binary-search-trees-ii/ where we are supposed to actually generate the BSTs. Thanks.

[@stonecoldcold2941]

code is not in the description!

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@alanliang9538]

good tutorial! (finally a tutorial with no indian accent)

[@BackToBackSWE]

hey

[@CostaKazistov]

1:39 made me laugh 🤌

[@mr.mystiks9968]

Skip to 7:00 if u already know the basics.

[@BackToBackSWE]

Ok

[@zzzz26526]

So at 10:58 G(0) does not yield any subtrees (if you have no nodes to begin with it's impossible) but you say it yields 1 because the result of the original problem is the cross product of the left and right side. So although G(0) is technically 0, you say it is actually 1.

[@jerrywu5797]

Highly appreciate your in-depth explanation! But I have trouble understanding the basic case when G(0) = 1. Given the description from Leetcode "Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?", n should not be zero, but in this solution it's a must to set G(0) = 1, or we cannot take the case when child node = nullptr into consideration. Is there any way to understand this? (It also occurs that for other dynamic programming problems, to set the base case value also bothers me!) Also, I am currently in the same situation as you are. I failed the final round interviews from Facebook and Bloomberg, which both are my dreamed companies. This is super frustrating but I have to keep working on these problems, because I believe with a deeper understanding of OOP design, algorithms and a bit of luck, I will get a job. Currently I started from scratch, reading the book Cracking the Code Interview and practice each problem with the help of Leetcode.( There are sometimes better solutions at Leetcode discussion tab than the ones given in the book!) Anyways, Thanks for your video. Best luck!

[@BackToBackSWE]

Yes. Ok, so when the problem says numbers from 1 to n it is has the hidden stipulation that n >= 1. What happens when n == 0? How do we adapt the description to that? Well if n == 0 then...we can't do the enumeration from 1 to n and therefore we have to implicitly understand that...if n == 0 then we will have no nodes to work with for out placements. No enumeration, no nodes. This is not just randomly saying G(0) = 1. When n is 0...we have no nodes to do anything with. What can I give back to you? Nothing. An empty tree. That IS SOMETHING. Therefore, when n == 0 we know that we will make 1 and only 1 unique tree...the empty tree. Does this clarify? Not sure if that answered your curiosities.

[@jerrywu5797]

@@BackToBackSWE Thank you for your quick reply! Yes i understand now. Considering the fact that when we do the calculation, we need to treat an empty tree as something exists. Therefore, by multiplying 1, it actually is one of the case s for all possible combinations(that is, left child node or right child node doesn't exist). Crystal clear now! Will check your other videos!! Thx my friend.

[@BackToBackSWE]

@@jerrywu5797 ok good. Yeah I'm on my laptop working on the channel/website/content/planning/a lot more, hence the quick reply.

[@shubhamsinnarkar2923]

Where is the code for this?

[@ky5069]

Serious remark: I've noticed your itching throughout the videos, so just a friendly reminder that if you have an itch in the entire body, you might want to check if you have habits that might overload your kidneys (food, activities, etc).

[@BackToBackSWE]

I have Eczema and the rooms at the library I shot videos at got hot. Weird comment to make.

[@sahil6567]

possibilities

[@BackToBackSWE]

yes.

[@swatigojra7904]

Everywhere this udemy ad is frustrating

[@BackToBackSWE]

lmao - I'm sorry. We will maybe remove ads when we hit 100k subs

[@ankitgoyal8556]

How to like video again ??

[@BackToBackSWE]

hack the API

[@ankitgoyal8556]

@@BackToBackSWE😂😂

[@kanav51]

Never thought that non Indians can make cool programming tutorials lmao.

[@BackToBackSWE]

hahaha, well they can now

[@sudheer-suri]

The way you explain is no where intuitive , it sucks bruh!

[@BackToBackSWE]

ok

[@mr.mystiks9968]

Initially it seems like the equation comes out of nothing but it actually is intuitive. You have to consider the question, if X is between 1-N, and I choose X to be the root then how many choices do I have for the left and right subtrees. Left subtree is 1 to (X-1) options. Right subtree is (X+1) to N options. The only thing that may be unclear is why we multiple the two G functions but if you try N = 3 and X as any value from 1 to N, then it becomes clear they must be multiplied else u get an undesirable answer. This is ultimately a counting problem and you have to question what your options are, notice a pattern between the options for the left and right subtrees, and write out a function to generalize it.