Lesson

Trees and Heaps

A binary tree has nodes with up to two children. The height is the number of edges on the longest root-to-leaf path. A heap is a complete binary tree with an ordering property: in a min-heap every parent is no larger than its children.

Practice

Q1

What is the height of a complete binary tree with $7$ nodes?

Show hint

7 nodes fill three levels.

Q2

What is the maximum number of nodes in a binary tree of height $3$?

Show hint

A full tree of height $h$ has $2^{h+1} - 1$ nodes.

Traversals visit nodes in a defined order. In-order traversal of a binary search tree yields the keys in sorted order.

Quiz

Q1

In a min-heap, where is the smallest element?

Show hint

The ordering property forces the minimum upward.

Q2

How many leaves does a full binary tree with $7$ nodes have?

Show hint

The bottom level holds the leaves.

Q3

In what order does an in-order traversal visit a node's subtrees and the node?

Show hint

In-order visits the root between its subtrees.