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

Key Takeaways

all right so today's question investigates when we're given a number n how many structurally unique binary search trees can we construct from the set of numbers from 1 to n so if n is 3 I'm only going to get the numbers 1 2 & 3 how many structurally unique binary search trees can I create with the numbers 1 2 & 3 3 nodes numbers one two and three again binary search trees everything on our left subtree is going to have to be less than the node we're sitting at everything in our right subtree is going to have to be greater than the node we're sitting at so why is this important this is actually a very important sequence in combinatorics and these set of numbers that this problem produces from its input of n forms the cattle and sequence or what's called the Catalan numbers and these are actually very useful in combinatorics I'll link below if you want to learn more about that but let's see how we can approach this question and I really want you to see the approach that I wanted to remind to be jumping to when we're approaching this problem and then we'll go over some formulas and terminology so that we can tackle this problem all right so now I want us to go through expansively going through a possibility set give it N equals 2 and our little bubble here we are able to use the numbers 1 where we'll choose the number 2 so we're going to have 2 nodes so my first choice is I need to choose a root number when I choose 1 as the roots this is what happens so when I choose 1 as the root I cannot have anything on the left because I can't put 2 on the left my bubble my realm of possibilities to put in the left subtree of 1 is none based on our possibility set we can't have anything in this left subtree and we've expanded all possibilities here but here now we have the possibility space of putting a 2 here so what materializes from this is we're going to be able to create ones tree so what is that tree so what materialized from that ability space was we put the one here and then we have a cloud of two and then we can place the two so this is if we choose one as the route we've expressed all possibilities of placements if we do one is the route with one as the route we can generate one tree it's right there and notice how when we go this way to go greater and value it's a binary search tree maintain those properties so we got one tree from planting one as the roots let's plant to as the root so we plant to as the root so what is going to happen what is going to be the branching of possibilities in our sub trees this is what the possibility clouds will look like and now we have a two rooted and this this expression right here expresses all the possibilities with two at the root all we can do is place the one in the right subtree and the left subtree has no possibilities to expand so now this is what we get so this is our answer this is the only structural unique binary search tree we can make given the numbers 1 & 2 if we plant two at the root and now we have another tree a notice that's our answer our answer is two the answer for the second Catalan number is going to be two because we can generate two structurally unique binary search trees so now let's expand our pool and let's expand to the number three and see how that changes how we do things so now n is three and I have the three numbers one two and three I can plant each at the root of my binary search tree and then I know the possibility spaces that will result from that choice so we choose one as the root and let's see what happens we chose one and an expression of all of the possibility space if I choose one I have a cloud here where I can put two or three at this node I can choose either because I will maintain the binary search tree property if I go right I can choose either of those at this node there is nothing choose there I cannot go lesser in value because the sequence starts at one so if I place with one at the root this is my new possibility space and notice I have two choices from here what do I do I will materialize both of those choices I really yield to trees from this so let's see what happens and now we have materialized this possibility space we have expressed both choices of two and three at that node and therefore we have maintained our BST property and I yield two trees from a placement of one at the root so now let's place two at the root and now I have placed two at the roots I have a one on the left and I need to express all of those possibilities and I have a three on the right so now what I do is I materialize those possibilities at each of these places we only can make one choice so I will materialize only one possibility from this so now all I can do is materialize this all I can do is get a to planted at the root and have a one on the left and may three on the right and now with two rooted at the root I know that I will yield one tree so now let's reach three at the roots and now I have put three at the roots notice my right subtree has no things I can put in it I'm going from 1 to 3 I do not have any choices for that node right there but for this node I can choose the 1 or the 2 so let's materialize each possibility so now I see when I have 3 rooted at the roots of a tree where I can use 3 nodes I know the answer is I can generate tune structurally unique binary search trees and now and now you see we have 5 and notice each of these are subproblems and when we see subproblems what does that remind me of what does that make me think it makes me think I can save answers I can use dynamic programming that is why this question turns out to be dynamic programming because each of these is a sub problem this sub problems answer is to what was the question if I plant one at the root and I have three nodes going from one to three what is the answer to if I plate to at the root and I have three nodes what is the answer one if I place three at the root and I have three knows what is the answer to so we are going to be sub probably down and to answer the nth Catalan number we are going to be building up our answers remembering past answers and then we are going to build up to a greater solution so now let's go into how we do that so we started our understanding at intuition so we knew a binary search tree works we knew when we place an element at the roots we're going to narrow how we can build trees so now let's formalize our ideas into equations so that we can understand mathematically how these subproblems are late so first let's define something so now let's define G of M so G of n is going to be the formula for the nth Catalan number it is the original question we are asked given numbers 1 to n how many structurally unique binary search trees can we build this is the overall question I can place one at the root I can place two or three I can place three at the root if n is three it is giving us from one to M so now let's define another equation that helps us understand what G of n means so now let's define the function f of I and M so with I at the root and n nodes available how many structurally unique binary search trees 10 I built so the answer to G of n is the sum if I plant V 1 V 2 V 3 and up to N at the root so if G is 3 I have 1 2 and 3 to work I can plant one at the root I can plant two at the root I can plant 3 at the root at each time I have three nodes total to work with so the answer to G of 3 is going to be the sum between these three plantings when we plant the 1 the 2 and 3 and explore all of those possibilities so how does this break down what does this look like as we build our possibilities through the tree so now this is what the breakdown looks like we're not changing anything we did this is exactly what we did before we have G of 3 our original question is for the third Catalan number so we plant one we plant - and we plant 3 but then what are the left and right subtrees what is their possibility space after we make this choice so now let's express that so this is a huge mental leap I need you to make so when we go left here when we plant one at the reach we can have nothing in the left subtree all the expressions are going to be G of 0 will have zero nodes to work with in this subtree we will have two nodes will have the two at the 3 to work with so therefore the amount of ways we can go from here is G of two we have two nodes we need all the unique placements within that subtree and that is going to express all of this and notice this continues to branch down we solve G OH - bison breaking it down here so we're going to solve this by breaking it down again into summations so moving on we know we can use the one in the left subtree if we plant two at the roots we know we can use three and the right subtree if we plant two at the root we have one node to work with G of one one node to work with G of one and then if we plant three at the root we have two nodes to work with in the left subtree one in two and we have zero nodes to work with in the right subtree because three is the maximum we only have three nodes one two three so now these are the key equations and guess what we already know the answer to G of zero just one we already know the answer to G of one it's just going to be one so this is how we subproblems breakdown and it yields us a key equation that brings us straight to coding it so finally this is how we do our dynamic programming the code is in the description now the code will make sense and you can see how the subproblems relate the answer to F planting at I on the root and having n nodes available the answer is the product this is actually called the Cartesian product because we are taking all of the cross-sections between two possibility spaces two possibility spaces we take the Cartesian product between them and what happens is we take the product between G of I minus 1 which we just take 1 minus 1 and we get 0 and then and - I if n is 3 and I subtract 1 from 3 I have 2 left so now G of 2 so all this is doing is saying left subtree possibilities right subtree possibilities multiply them to take all the cross section between the possibilities and that gives us all of these structurally unique binary search trees we can build given that we rooted at this specific element this is the final intellectual jump you need to make to fully understand this problem and how the dynamic programming gives us the answer to this global solution this is the bigger picture of this question so if I plant a 2 at the root and N equals 3 I play it into 2 at the root the reason I subtract 1 is because I can go from 1 up to the 2 minus 1 because we're going to the left it's a binary search tree we need to go down in value and if I go to the right we subtract from our upper bound we know that and minus the 2 is going to yield us the amount of nodes we can work in the right subtree because that gives our us our upper bound our right bound so now that we see the bigger picture and again you don't need to immediately internalize this but this is the bigger picture I want you to understand let's look the time and space complexity to this solution so we're going to let n be the input n and the time complexity is going to be Big O of N squared but don't ever be fooled when you ce o-- of N squared that does not mean for every single n we do n iterations the thing is it might be a triangular sort of work when we drop a constant maybe it's like 1/2 N squared there's a much more detailed and mathematical analysis of the time in the description below provided by Li code I don't want to go into it here because I probably explained it wrong but our time complexity is going to round to N squared and then our space complexity is going to be linear we are going to be storing the solution to n plus 1 subproblems if you count the 0 with subproblem if you don't we're just starting and subproblems either way it does not matter we will scale in a linear fashion as the input size the n gets arbitrarily large for this problem so these are the time and space complexities if this video helped you if this was a clear explanation subscribe to the channel and like this video these are for you to prepare for the software engineering interview and to just excel in it and do well so subscribe to the channel like the video and [Music]