let's solve leak code 96 unique binary search trees so we're given an integer n in this example we're given the integer 3 and we want to know how many unique binary search trees can we make from these integers so this sounds like a pretty simple problem right so let's think about the most simple case what if we were given just one number and let's say it was 1 then we can only make one search a binary search tree with this right just 1 as a root node ok what if we were given two numbers 1 & 2 there's two trees we could make with this right what if the root node was 1 in that case we have a root 1 and then we can only put the 2 in the right subtree right because that's how a binary search tree works so that this is one solution another one is what if 2 was the root of this tree then we can only put the 1 in the left subtree because that's how a binary search tree works so summarizing what we know if we had the number of nodes so in this table if we had one node then we would only have one tree if we had two nodes we would have two trees now in this example they even tell us if we have three nodes then we can only have five trees but the question is how can you figure this out let's take a look at if we had three nodes so let's say we have three values 1 2 & 3 now if we had 1 as the root node that means we have to put these two values in the right subtree of 1 now they could be ordered in two different ways obviously we could have two as the root or two as the parent and then 3 as the child or we could have 3 as the parent and then 2 as the left child do you kind of notice how the numbers themselves don't matter whether it's a 2 and a 3 or it's a 1 and a 2 the number of trees we can make from it is the same regardless of what the values are now if we had two as the root then we only have one possible way right we have to put the one in the left subtree and we have to put the the three in the right subtree if our three is the root though then we got to put both of these in the left subtree so it's kind of symmetrical to what happened when one was our root remember we had to put these two values in the right subtree but now we're doing the opposite three is the root so we got to put one and two in the left subtree it could either be like this or it could be like this basically this is a recursive problem right assuming we had an arbitrary number of values right 1 2 3 4 5 and some other value we have to consider that each value could be the root at some point right so for example let's say 2 is the root then that means one value is going to go in its left subtree and three values are gonna go in the right subtree so then the result of this becomes so how many trees could we have where 2 is our root and then let's say we have two sub trees well it's gonna be the number of trees we can make from just one value right so number of trees with just 1 as the input so with one value and we already know that right that's the base case with only one node you can only have one tree that's pretty easy what about 3 what if we have 3 nodes in our right subtree well if we compute that before number of trees in the right subtree let's say we already know that because we kind of do right we just computed that here we know it's 5 so then we can take these 2 values and multiply them together because we're getting the total number of combinations right and since we want the number of combinations we have to multiply that's just the rule right and we have to do this for every single root so in the case where 1 is the root if 1 was our root then that means in the left subtree there's nothing here right so the number of trees of 0 now with zero that's also kind of a base case if you have no nodes well you can only have one possible tree right and in the right subtree we have four different values so we want the number of trees we can get with four values and we're going to multiply these together again and we're basically going to take these multiplications that we're doing and we're going to do that for every single value considered as the root node and we're going to sum them up so the thing another thing to notice is that if we want to compute the number of trees of let's say four then to compute that we have to have the number of trees of one number of trees of two number of trees of three nodes as well because we know that the sub trees could be this large as well as 0 of course but that's a base case that we don't really have to compute now since we're doing this this is kind of like a dynamic programming problem right you solve the subproblem so for example how many trees could you make with one node and then you solved how many you could make with two nodes three nodes up until we get to n now the time complexity of this is I think Big O of N squared because if we want to compute the number of nodes a number of trees we can make with four nodes for example we got to iterate through the entire list of four numbers considering each number as the root node and if we wanted to do that for three nodes we'd have to do the same thing and so since we are doing it in order right from one to two to three all the way up into n it's going to be oh of N squared now for space complexity it's also we are using some space because we're gonna store the result where we don't want have to recompute how many trees we can make with four nodes for example so we're gonna store that result we're gonna store it for each value from 1 to n so it's going to be big of n space complexity so now let me show you the code and it might be even more easy to understand ok so now let's look at the code let me write a comment to really show you exactly what we're gonna do so for example if we wanted the number of trees for for example with four nodes we would get considering each value is the root node so for example the firt if we considered the first value as a root we get a left subtree with zero nodes in it and we get a right subtree of three nodes in it and we want to multiply those together and then with this we want to add another one because we could consider the second value as the root node in that case our left subtree would have one value in it and our right subtree would have two values in it remember we have a total of four nodes so the root is one node the left subtree has one node and the right subtree has two nodes and we can keep doing this considering each of the four values as the root node if the third value is the root node we'd have two values in our left subtree and one value in the right subtree if the last the fourth value was the root node we'd have three values in our left subtree and one value in our right subtree so with this in mind i'm going to go straight into the dynamic programming solution so remember we're going to compute the number of trees from each number from zero all the way to n so i'm going to have an initial array which i'm going to initialize with ones and it's going to be the length of n plus one because we're going from 0 to n and we remember the base case one or zero nodes equals one tree right the empty tree one node is also one tree with just one root node right so we don't have to compute those we can start right at two so for starting at two the number of nodes is in range of two all the way to end okay and now we want to consider each of these nodes as the root node so for example in the first iteration nodes is going to be two we want each we want to consider each of those two values as the root so we're gonna go through in range from one all the way to number of nodes and from this remember we're computing this big sum up over here so I'm going to declare a variable called total to compute that sum which I'm going to initially say is zero the reason we initialize our array to all ones is for this these two base cases pretty much so each iteration of this loop I'm gonna add two total so I'm going to take number of tree so how do we get how many are in the left subtree and how do we get how many are in the right subtree let's compute that so the left subtree is basically going to be root minus one because for example if we were taking the third node as the root then the left subtree would have two nodes three minus one the right subtree is going to be the total number of nodes - what root node we have for example if we had four total nodes and the root node was the second node we'd have four minus two meaning two nodes are in the right subtree so knowing that let's compute the total let's update our total so we're gonna get the number of trees that we can make with the left number of nodes multiplied by the number of trees we can make with the right number of nodes the nodes that are on the right subtree and we're gonna add that to total now at the end we're gonna take this total and put it into our cache which i've called number of trees number of trees of these number of nodes so for the first iteration of the loop it's going to be two nodes is going to be mapped to the total so we're going to do that we're going to compute the number of trees we can get all the way from one to n and so at the end remember we just have to return the one result number of trees we can make with n nodes the input was n and we can return we can submit this code and I'm gonna pray that it works hopefully I don't have a bug and it works perfectly because I just did this 18 minutes ago so I really hope this was helpful we went straight to the dynamic programming solution we didn't do any recursion or anything but I think this is a straightforward enough problem that you can understand from the dynamic programming perspective if this was helpful please leave a like and subscribe and thank you for watching