[Chicago] A fun problem using a binary tree.

[Adam Forsyth]

The depth of the tree is 1000 / 50 + 1 = 21

The average node value is 1000, because you subtract the same amount from
the left child as you add to the right child.

The number of nodes is 2 ^ depth - 1 -- so in this case, 2 ^ 21 - 1 = 2097152
- 1 = 2097151

The total sum = number of nodes * average node value = 2097151 * 1000 =
2097151000.



On Sat, Mar 28, 2015 at 2:02 AM, Lewit, Douglas <d-lewit at neiu.edu> wrote:

> I'm just starting to learn about binary trees in my data structures
> class.  Interesting!  Just as I'm getting used to linked lists, the plot
> thickens and becomes even more complicated!  Oh geez!
>
> Here's the problem.  The root has a value of 1,000.  Every left child is
> 50 less than its parent, and every right child is 50 more than its parent.
> Continue adding nodes and children until finally the leftmost node (a leaf)
> has a value of 0.  Then add up all the nodes!  What is the total sum?
>
> I used Python 2.7 to solve the problem, although I believe my code is
> equally legit for Python 3.#, but try it and let me know.  I hope my answer
> is right!  I'm still confused about this whole tabs vs. spaces issue.
> What's the difference.  I mean.... as long as the interpreter doesn't yell
> at me, why should I worry about the difference between tabs and spaces?
>
> I believe that Java has a built-in class for constructing trees.  Does
> Python have such a built-in data structure?  If it does I don't know about
> it.  I created my own binary tree structure.  Cool stuff.
>
> Thanks for the feedback.
>
> Best wishes,
>
> Douglas Lewit
>
> _______________________________________________
> Chicago mailing list
> Chicago at python.org
> https://mail.python.org/mailman/listinfo/chicago
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/chicago/attachments/20150328/556ece9e/attachment.html>