i have this question for an assignment, but this has to be a typo right?
13.2 Draw all possible binary trees that contain 12 nodes.
there is like over 200k possible binary trees for this, am i misunderstanding something?
#🔒 binary trees
visual meteor
wintry obsidianBOT
i have this question for an assignment, but this has to be a typo right?
` 13.2 ...
@visual meteor
Python help channel opened
slow dawn
i have this question for an assignment, but this has to be a typo right?
` 13.2 ...
Yes, that looks off. Maybe all balanced binary trees? There would still probably be a ton of those though.
visual meteor
this from the book "data structures and algorithms using python" by Necaise:
visual meteor
Yes, that looks off. Maybe all *balanced* binary trees? There would still probab...
i looked into this and i can calculate how many possible trees we can have using something called catalan numbers?
so im not sure if maybe thats what they meant
slow dawn
i looked into this and i can calculate how many possible trees we can have using...
Honestly, it's been like 10 years since I've formally studied binary trees, so I forget most of the terminology. I meant, they might be ruling out unbalanced trees that are effectively linked lists, and are only counting trees where every node's children are the same height.
tulip cloak
i need help
manic osprey
Given 13.1, I think not.
manic osprey
And they're not just asking for a count, but to draw them. Even just generating them seems.... burdensome.
visual meteor
the professor hasnt responded in a week since we've been off for holiday but this is due tomorrow
manic osprey
And thoughts from other students in the class? Any more context around these questions?
visual meteor
writing could that could generate them recusively makes more sense but still really tedious i think
no everyone in the class discord is stumped as well
the hw had 2 portions this part was ripped directly from this book
manic osprey
You could skip it and move on. If you want to have some kind of answer, write a paragraph about how this seems to want many trees, and maybe provide an estimate of the total number.
tulip cloak
someone help me with my project no one wants to help me I'm lonely
visual meteor
would this work for calculating the estimate:
manic osprey
someone help me with my project no one wants to help me I'm lonely
Please open a separate thread with a specific question.
visual meteor
it seems right? but ive never heard of this before my math is a bit weak
manic osprey
I have that page open right now. They might be relevant, haven't figured that out yet.
manic osprey
If you just want to compute the total number that's probably tractable:
- all the trees with 12 nodes down the left and 0 nodes on the right
- all with 11 on the left and 1 on the right
- all with 10 and 2
- so on
If you cache the answers for each (a,b) pair it will go much faster.
visual meteor
would a,b just be opposites?
manic osprey
Given that the numbers for (a,b) and (b,a) are the same, that's 72 counts to cache.
visual meteor
what do you mean by cache in this context?
manic osprey
When you go to compute the count for a-left and b-right, have a lookup table of previously computes pairs. If it's there, you can just reuse the number. If not, compute it and save it just before returning it.
Eg a dict keyed on (a,b).
slow dawn
would this work for calculating the estimate:
Just for shits'n'giggles, I asked an AI to see what they say. They agree with you:
manic osprey
Right. So again, I'd skip this, possibly with an explaination of why, and move on.
visual meteor
When you go to compute the count for a-left and b-right, have a lookup table of ...
is this kind of like recursion?
or rather can it be treated as such
manic osprey
It's recursion with a short circuiting lookup to avoid recursing the same answer a second time.
The tree counting is recursive. The cache is kind of orthoganal to that, but effective in the recursive scenario.
Since any recursive function has the form:
- for trivial cases, return the trivial answer
- for other cases, compute a smaller version of the problem and combine for the answer to this case
The values in the lookup table are thus "trivial cases", because their value is known
manic osprey
Not sure what you mean there.
visual meteor
like how in recursion to fill a call stack and then pop out each operation as you return them once you reach the base case
manic osprey
The recursive calls to the function do that for you.
visual meteor
in your example it sounds like each time you compute the smaller version (e.g. recurse) your effecitively outputting one of your answers (a binary tree)
manic osprey
Well, you "output" it to the cache, for reference later. But you also return it as the result of the function call.
visual meteor
ah ok
manic osprey
You share the cache across all the calls as a parameter.
visual meteor
ohh wait right because u need to reference that to ensure youre not repeating it
that was the "short circuiting" u were refering to right?
manic osprey
Yes: if the answer's in the lookup table you return it immedaitely (trivial case) instead of recursing to compute it.
visual meteor
thats super interesting i havent seen recursion implemented like that yet (im very new to this lol)
its almost like a search algorithms built in
is this how search trees work?
manic osprey
Well, it's a combination of recursion (for the computation) and a cache to avoid recomputation.
manic osprey
is this how search trees work?
Kind of. I'd need a specific example.
manic osprey
Searching a binary tree tends to be iterative because you don't need to consider multiple branches. So you go:
- is it this node? yes, return it
- no? consider the left or right node depending
You can do that in a loop with a variable for the current node. Repeat until found or no child node.
visual meteor
how does it know when to stop?
manic osprey
No child nodes.
visual meteor
or how to go from a child to its children (if it has any)
ahhh
ok
but what if they siblings?
i guess it checks that too
it probably checks the depth of the node and compares to the height of the tree
manic osprey
Not sure what you mean. Think about searching for 42 in the above tree. You start at 60. Not a match, go left. 12? no, go right. 41? No, go right. Oh there's no right. You're done - the key is not present.
... making coffee, back in a sec ...
visual meteor
Not sure what you mean. Think about searching for 42 in the above tree. You star...
oh i see, u go left because its smaller than 60
then once u get to 41 if theres no right then it means it doesnt exist since only numbers less than 41 are possible after that point
manic osprey
Right.
wintry obsidianBOT
Python help channel closed