BeginnerCoder
Donate← Data Structures
10 / 25
Lesson 10 — Binary tree: size and height
Binary tree: every node has up to two children
A tree is a hierarchy: one root at the top, each node has children, and nodes with no children are leaves. In a binary tree each node has at most a left and a right child. Trees are naturally recursive: the height of a tree is 1 + the height of its taller subtree, and an empty tree has height 0.
def height(n):
if n is None:
return 0
return 1 + max(height(n.left), height(n.right))
Why it matters: folders on your disk, HTML pages and company org charts are all trees.
Want it another way?
Task
Finish count(n) the same way height() works: an empty tree has 0 nodes, otherwise 1 + count(left) + count(right).
Run your code — when the output matches the task, you will see a green check. Then mark the lesson complete.
Test your knowledge
Test your knowledgeA quick 3-question quiz on this lesson — instant feedback.