Paul's Python CoursePPC

Trees

Not met yet

A tree is a card with cards below it, each of which has cards below it, down to leaves with nothing below. The top card is the root. The height is how many levels there are from the root down to the deepest leaf: 0 for an empty tree, 1 for a single card. Every side of a tree is a smaller tree, so tree code is usually recursive: an empty side gives the base case, and a card's answer is built from the answers for its sides.

Try it

main.py

Output

Press Run and what your program prints shows up here.

Easy to get wrong

  • Thinks a tree's height is how many cards it holds, rather than how many levels from the root to the deepest leaf.
  • Thinks an empty tree has a height of 1, so every height comes out one too many.
  • Thinks the root is a leaf, or that leaves are the cards nearest the top, rather than the cards with nothing below them.

Where it comes up