CTCI 4.9 BST Sequences - Java

[@PradeepSingh-vm1gl]

Great. Thank you.

[@Mohammad-wo7yi]

Thanks for the explanation! What do you think the time complexity is? Intrestingly enough the CTCI solution ignored the time complexity discussion altogether.

[@KacyCodes]

Yeah I noticed that too. I think because it involves combinatorics math. Roughly off the top of my head, a balanced tree is the worst case for total # of combinations (that’s intuitive because the more unbalanced it is the closer it gets to being a linked list which only has 1 combination). So then you’d have to figure out the time complexity of each function call assuming the input is a balanced tree, and multiply that by the number of combinations. Now how do you figure out the total number of combinations? I would do the leetcode 1569 and try to come up with a time complexity for that problem, then come back to this one. If you want to figure out the time complexity for yourself that’s great, but if you’re doing it because you want to know for an interview, chances are you’re going to be one of the few that can even solve this particular problem, so knowing the time complexity would just be icing on the cake.

[@OhYamz]

So at each height/level you're going to have 2^height nodes (roughly). So let's say nodesAtLevel = 2^height. You know at each level then, that the number of permutations for that level of the BST will be roughly nodesAtLevel! (factorial). Would it be possible to do a breadth first search pass through the tree, at each level simply build new lists from the previous permutations: root => 1! => [9] level2 => 2! => [9] + [3, 15] , [9] + [15, 3] level3 => ~4! => [9, 3, 15] + [all permutations of nodes at level3], .......... , [9, 15, 3] + [all permutations of nodes at level3 again] allSequences would essentially be [1!] + [2!] + [4!] + ... + [nodesAtLevel!] I haven't thought it all the way through. Not quite sure how you would store all the lists and start new lists when needed.