AI Hints
Home›DSA in Python Tutorial›Measuring and Searching Trees
DSA in Python · Lesson 64 of 132

Tree Size and Height

Recursive measurements.

⏱ 2 min read▶ Video at 1:15:18🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Trees and recursion are made for each other. A tree is a node, with two smaller trees hanging below it. So most tree questions have the same answer. Ask the left subtree, ask the right subtree, and combine.

Tree Size and Height
From the video: Tree Size and Height
  • A tree is made of smaller trees
  • Ask left, ask right
  • Combine the answers

Size, height and total

The size of a tree is one, for this node, plus the sizes of both subtrees. Its height is one, plus the taller of the two subtrees. And the total is this value, plus both totals. An empty tree is the base case for all three, and gives zero. Run it.

measure.pypython
from tree import sample

def size(n):
    return 1 + size(n.left) + size(n.right) if n else 0

def height(n):
    return 1 + max(height(n.left), height(n.right)) if n else 0

def total(n):
    return n.value + total(n.left) + total(n.right) if n else 0

root = sample()
print("size:", size(root), "height:", height(root), "total:", total(root))
Output
size: 9 height: 4 total: 66
Also uses tree.py
class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def sample():
    return TreeNode(8,
        TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
        TreeNode(10, None, TreeNode(14, TreeNode(13))))

PICTURE = '        8\n      /   \\\n     3     10\n    / \\      \\\n   1   6      14\n      / \\    /\n     4   7  13'

The tree recipe

Almost every tree function has this shape. If the node is empty, return the base answer. Otherwise, call the function on the left child, then on the right child, and combine the two answers with this node. Each node is visited once, so it's O of N.

keyvalue
Empty nodebase answer
Leftrecurse
Rightrecurse
Combinewith this node

Summary

Size, height, and total all follow one recipe. Ask both subtrees, then combine. Next, a special tree that keeps values in order. The binary search tree.

Key takeaways
  • size = 1 + left + right
  • height = 1 + max(...)
  • Empty tree = 0
Next up: Binary Search Trees — smaller left, bigger right