pathetic piss kitten (@kitten)

what was the way to count the number of nodes in this kind of structure?

@kitten as in, a tree? write a recursive function that counts how many nodes are in a particular subtree

@kitten

data Tree a = Leaf | Node (Tree a) a (Tree a) -- left, value, right

count (Node l _ r) = 1 + count l + count r
count Leaf = 0 -- or 1 if leaves count as a node

@dpk what language is this :blobCat_eyes:

like, I know, by checking different depths, that the count is always (2^depth+1)-1

but that feels wrong :blobwtfnotlikethis:

@kitten only when balanced though. if un-balanced you're stuck with a recursive count iirc

@mindpersephone this is just for a unit test so that'll do for now

@kitten in case of the full tree, you can actually prove this by induction!

(slightly harder exercise: what's the sum of the depths of all the nodes? what about the sum of the lengths of all the paths in the tree, between all pairs of nodes? (i do wonder if there's a nice combinatorial proof for the last one...))

@kitten as far as the count of nodes in a full binary tree goes, you could also give a combinatorial argument for why it's 2^(depth+1) - 1:

first let's count the nodes in the k-th layer of the tree. each node can be identified with a path that starts at the root, and takes k steps downwards. at each step, you can make an independent choice between going either left or right, so there are 2^k nodes at the k-th layer

how about the full tree of depth n? the obstacle here is that the nodes at different depths have different depths of the paths used to reach them. but we can consider them all as sequences of instructions of length exactly n+1, as follows:

- we start above the tree, waiting for now.
- at each step, we decide to either WAIT, or GO — at which point we enter the tree at the root
- once we decide to go, we spend the rest of our time going either LEFT or RIGHT at each step
- we only stop once the time runs out

observe that:

- at each of the n+1 steps, we have 2 choices, so there are exactly 2^(n+1) such sequences of instructions
- for each node of the tree, there is exactly one sequence that ends up there: for a node of depth k, it's WAIT for n-k steps, then GO, and k steps of either LEFT or RIGHT
- however, there is one sequence that doesn't ever end up at any node: the one that spends all the time WAITing, never deciding to GO. thus, there are 2^(n+1) - 1 sequences that actually address a node in the tree

mx @kitten, true! we can prove this by induction on the depth.

for depth = 0, there is exactly one node, and 2^(0+1)-1 = 1. so the formula works in the base case.

now suppose we know it is true for all trees up to a given depth d. a tree with depth d+1 looks lik two trees of depth d connected by an additional node. so the number of nodes is two times the number of nodes in a tree of depth d, plus one. 2*(2^(d+1)-1) + 1 = 2*(2^(d+1)) - 2 - 1 = 2^((d+1)+1) - 1, showing that the formula holds for depth d+1 if it holds for depth d.

by induction, we conclude the formula is true for all depths ≥ 0.

@1 but it doesn't feel right :neocat_cry:

@1 wait

no, it actually does feel right

mx @kitten, why not? the sum of a geometric sequence in base n is, up to accounting for starting and ending points, n to the power something.

another proof: let the sum S be equal to 1 + n + n^2 + ... + n^d. then nS = n + n^2 + ... + n^(d+1). so nS - S = n^(d+1) - 1. divide by n - 1 on both sides to get S = (n^(d+1) - 1) / (n - 1).

for n = 2, n - 1 = 2 - 1 = 1, so the sum is 2^(d+1) - 1, as we expected.