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

Поделиться
HTML-код
  • Опубликовано: 18 сен 2024

Комментарии • 162

  • @BackToBackSWE
    @BackToBackSWE  5 лет назад +15

    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
      @AhmedAli-jx9ie 4 года назад +1

      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
      @BackToBackSWE  4 года назад +1

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

  • @florencechan8863
    @florencechan8863 5 лет назад +175

    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
      @BackToBackSWE  5 лет назад +13

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

    • @vincentkoo4453
      @vincentkoo4453 4 года назад +6

      This post helped me a lot, thank you very much

    • @BackToBackSWE
      @BackToBackSWE  4 года назад +2

      @@vincentkoo4453 nice

    • @eug_gino
      @eug_gino 4 года назад +7

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

    • @BackToBackSWE
      @BackToBackSWE  4 года назад +3

      @@eug_gino I support

  • @kevinnguyen9397
    @kevinnguyen9397 5 лет назад +24

    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
      @BackToBackSWE  5 лет назад +12

      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
      @yousufhussain9530 2 года назад

      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
    @ankitgoyal8556 4 года назад +4

    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.

  • @SamM-ne5uq
    @SamM-ne5uq 5 лет назад +2

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

  • @yuvrajjagga9351
    @yuvrajjagga9351 5 лет назад +2

    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
      @BackToBackSWE  5 лет назад

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

  • @soymaxxing
    @soymaxxing 5 лет назад +4

    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

  • @waleedahmed1725
    @waleedahmed1725 4 года назад +4

    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!

  • @Oleks380
    @Oleks380 5 лет назад +5

    Thank you man! You're doing a great job

  • @tumul1474
    @tumul1474 4 года назад +2

    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 !!

  • @snowy0110
    @snowy0110 Год назад

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

  • @jishulayek8252
    @jishulayek8252 5 лет назад +3

    You are an amazing teacher !!! Loved it

  • @girishthatte
    @girishthatte 4 года назад +2

    Perfect and concise explanation

  • @jianxiaohu8213
    @jianxiaohu8213 5 лет назад +4

    Thank you, that was so well explained!

  • @omnya9381
    @omnya9381 4 года назад +4

    Amazing explanation!!! Thank you so much

  • @aynurmukhambetova1708
    @aynurmukhambetova1708 4 года назад +1

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

  • @markgraham2312
    @markgraham2312 3 года назад +1

    It was a good explaination. Thank you.

  • @nirankarojha2660
    @nirankarojha2660 4 года назад +2

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

  • @TheGizmoTruck
    @TheGizmoTruck 4 года назад +1

    year later, this is still helpful. Thank you

    • @BackToBackSWE
      @BackToBackSWE  4 года назад

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

  • @OP-yw3ws
    @OP-yw3ws Год назад

    Thanks for the awesome explaination!!!

  • @maripaz5650
    @maripaz5650 3 года назад +1

    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.

  • @כפירכהן-נ8ע
    @כפירכהן-נ8ע 4 года назад +2

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

  • @ivantishchenko4686
    @ivantishchenko4686 4 года назад +2

    Superb explanation!

  • @chintangotecha7089
    @chintangotecha7089 5 лет назад +3

    Great explanation. Highly appreciated :)

  • @Rahul-uk4su
    @Rahul-uk4su 3 года назад +1

    This was super helpful thanks. I liked the video

  • @annettejohn6829
    @annettejohn6829 3 года назад

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

  • @nithishkumar2561
    @nithishkumar2561 2 месяца назад

    Great explanation bro

  • @gokulgopinath3777
    @gokulgopinath3777 3 года назад

    Great explanation

  • @amitmehta2285
    @amitmehta2285 2 года назад +1

    I love you you helped me really

  • @kxiong4021
    @kxiong4021 4 года назад +1

    Thanks for the explanation!!

  • @karansagar7870
    @karansagar7870 4 года назад +1

    Gr8 explanation

  • @ZackOfAllTrad3s
    @ZackOfAllTrad3s 5 лет назад +2

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

  • @kunqian06
    @kunqian06 5 лет назад +1

    Thanks for the awesome explanation

  • @Gabriel-ms6qw
    @Gabriel-ms6qw 4 года назад +2

    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.

  • @fastisslow6177
    @fastisslow6177 3 года назад

    Nice and powerful explanation.

  • @jinhopark3671
    @jinhopark3671 3 года назад

    Great explanation. Thanks!

  • @aikolkoikelov7514
    @aikolkoikelov7514 3 года назад

    Thanks man for a such clear explanation )

  • @vivil7917
    @vivil7917 3 года назад

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

  • @sudhakar104624
    @sudhakar104624 5 лет назад +1

    Awesome explaination

  • @punitpawar4231
    @punitpawar4231 4 года назад +1

    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
      @BackToBackSWE  4 года назад

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

  • @rohan8arora
    @rohan8arora 4 года назад +2

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

    • @BackToBackSWE
      @BackToBackSWE  4 года назад +1

      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.

  • @jayeshmarathe7678
    @jayeshmarathe7678 3 года назад

    video on Optimal binary search tree please

  • @TheSteak1984
    @TheSteak1984 3 года назад

    Big Thank You!

  • @VijayKumar-bp1fp
    @VijayKumar-bp1fp 4 года назад +1

    very good explanation...

  • @Code4You1
    @Code4You1 2 года назад

    Thank you bro!

  • @weibangzhang3994
    @weibangzhang3994 4 года назад +1

    great work

  • @chris.w391
    @chris.w391 3 года назад

    Best explanation

  • @nishanth998
    @nishanth998 4 года назад +1

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

    • @BackToBackSWE
      @BackToBackSWE  4 года назад

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

  • @jyotisingh8183
    @jyotisingh8183 4 года назад +2

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

    • @BackToBackSWE
      @BackToBackSWE  4 года назад

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

  • @vedankgoyal1706
    @vedankgoyal1706 4 года назад +1

    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
      @BackToBackSWE  4 года назад +1

      ye

    • @persianwaffle
      @persianwaffle 4 года назад

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

    • @vedankgoyal1706
      @vedankgoyal1706 4 года назад

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

  • @motivation_hubPJ
    @motivation_hubPJ 4 года назад +1

    Thanks a lot bro

  • @大盗江南
    @大盗江南 5 лет назад +1

    Thank u super much man!

  • @RodrigoVillarreal
    @RodrigoVillarreal 5 лет назад +2

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

    • @BackToBackSWE
      @BackToBackSWE  5 лет назад

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

    • @harsaroorabhyankar
      @harsaroorabhyankar 5 лет назад +1

      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.

  • @xxbighotshotxx
    @xxbighotshotxx 5 лет назад +1

    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.

  • @taiwan.1
    @taiwan.1 5 лет назад +2

    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
      @BackToBackSWE  5 лет назад +1

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

    • @taiwan.1
      @taiwan.1 5 лет назад +1

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

    • @BackToBackSWE
      @BackToBackSWE  5 лет назад +1

      @@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

  • @CostaKazistov
    @CostaKazistov 2 года назад

    1:39 made me laugh 🤌

  • @christiansakai
    @christiansakai 5 лет назад +2

    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
      @BackToBackSWE  5 лет назад +1

      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
      @christiansakai 5 лет назад

      @@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.

  • @SidharthJhawar
    @SidharthJhawar 5 лет назад +1

    Subscribed!!!

  • @alirezaRahmanikhalili
    @alirezaRahmanikhalili 5 лет назад +1

    good job

  • @mr.mystiks9968
    @mr.mystiks9968 4 года назад +1

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

  • @zzzz26526
    @zzzz26526 3 года назад

    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.

  • @zzzz26526
    @zzzz26526 3 года назад

    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?

  • @lewisben6697
    @lewisben6697 5 лет назад +1

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

  • @alanliang9538
    @alanliang9538 4 года назад +2

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

  • @stonecoldcold2941
    @stonecoldcold2941 4 года назад +1

    code is not in the description!

    • @BackToBackSWE
      @BackToBackSWE  4 года назад

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

  • @ky5069
    @ky5069 4 года назад +2

    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
      @BackToBackSWE  4 года назад +1

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

  • @heisenberg1844
    @heisenberg1844 3 года назад

    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.

  • @shubhamsinnarkar2923
    @shubhamsinnarkar2923 3 года назад

    Where is the code for this?

  • @jerrywu5797
    @jerrywu5797 5 лет назад +2

    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
      @BackToBackSWE  5 лет назад +4

      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
      @jerrywu5797 5 лет назад +1

      @@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
      @BackToBackSWE  5 лет назад +1

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

  • @ankitgoyal8556
    @ankitgoyal8556 4 года назад +1

    How to like video again ??

  • @swatigojra7904
    @swatigojra7904 4 года назад +1

    Everywhere this udemy ad is frustrating

    • @BackToBackSWE
      @BackToBackSWE  4 года назад +2

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

  • @sahil6567
    @sahil6567 4 года назад +1

    possibilities

  • @kanav51
    @kanav51 5 лет назад +4

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

  • @sudheer-suri
    @sudheer-suri 4 года назад +1

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

    • @BackToBackSWE
      @BackToBackSWE  4 года назад

      ok

    • @mr.mystiks9968
      @mr.mystiks9968 4 года назад

      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.