Skip to content
Tutorials Center
My learning

Topics

Lesson 47 of 68 ยท Graph Theory

Binary Tree Traversals and Huffman Coding

Visit binary trees in preorder, inorder, postorder and level order, evaluate expression trees, and build prefix codes with Huffman's algorithm in Python.

A tree is only useful if you can visit its nodes in a well-defined order. Binary trees, where every node has at most a left and a right child, power expression parsers, search structures and compression formats. In this lesson you will learn the four standard traversals, see how an expression tree turns into prefix, infix and postfix notation, and then meet prefix codes and Huffman's algorithm, which builds an optimal one with a priority queue.

Here we use the basics from Trees and Spanning Trees: a rooted tree, parents, children and leaves. A binary tree limits each node to two children, called left and right.

Four ways to visit a binary tree

Three traversals are depth-first and differ only in when the node itself is visited relative to its two subtrees:

  • Preorder: node, left subtree, right subtree.
  • Inorder: left subtree, node, right subtree.
  • Postorder: left subtree, right subtree, node.

The fourth, level order, is breadth-first: visit all nodes at depth 0, then depth 1, and so on, using a queue.

Python The four traversals

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Where the node goes

Preorder Node first, then left, then right.
Inorder Left, then node, then right.
Postorder Left, right, then node last.
Level order Row by row, using a queue.

For a binary search tree, inorder gives sorted order.

1 / 2

A useful fact: a preorder list together with an inorder list identifies a binary tree with distinct labels uniquely. Preorder tells you each root first; inorder tells you how many nodes lie to its left.

Expression trees

An arithmetic expression is a tree: leaves are numbers or variables, internal nodes are operators. For (3 + 4) * 2 - 5, the root is -, with a left child * and a right child 5; the * has children + and 2; the + has children 3 and 4.

Each traversal produces a notation:

  • Inorder gives the usual infix form (with parentheses added around each subtree).
  • Preorder gives prefix (Polish) notation: - * + 3 4 2 5.
  • Postorder gives postfix (reverse Polish) notation: 3 4 + 2 * 5 -.

Prefix and postfix need no parentheses at all, which is why stack calculators and compilers like them. Evaluating a tree is a postorder walk: compute both subtrees, then apply the operator.

Python Expression tree: notations and evaluation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Prefix codes

To store text compactly, give common symbols short bit strings and rare ones long strings. Fixed-length codes waste space on skewed data, but variable-length codes raise a problem: if a = 0, b = 01 and c = 1, then 01 could be b or ac. The fix is a prefix code, where no codeword is the start of another. Then a bit stream decodes uniquely without separators.

Any prefix code is a binary tree: each left edge is 0, each right edge is 1, and the symbols sit at the leaves. The codeword of a symbol is the path from the root. Because symbols are only at leaves, no codeword can be a prefix of another.

Huffman's algorithm

Given symbol frequencies, Huffman's algorithm builds the prefix-code tree with the smallest total length for the whole message:

  1. Make a leaf for each symbol, weighted by its frequency.
  2. Repeatedly take the two lightest trees and join them under a new parent whose weight is the sum.
  3. Stop when a single tree remains.

The rule is greedy: rare symbols end up deep (long codes), frequent symbols stay near the root (short codes). A priority queue keeps this fast, O(n log n) for n symbols. Huffman codes are optimal among all symbol-by-symbol prefix codes.

Python Building a Huffman code

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The most frequent symbol, a, gets the shortest code. The encoded message takes 55 bits instead of the 80 a fixed 4-bit code needs (ten distinct symbols), and the decoder recovers the text without any separators because no code is a prefix of another. Compression tools such as DEFLATE (used in ZIP and PNG) rely on Huffman coding as one stage; see also the Huffman lesson in DSA for a data-structures view.

The tree must be shared with the decoder: real file formats store the code lengths in a header. A message with a single distinct symbol is a special case, handled above by giving it the code 0.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which traversal visits a binary search tree's keys in sorted order?

    Inorder visits the left subtree (smaller keys), then the node, then the right subtree (larger keys).
  2. 2. Which traversal of an expression tree yields postfix notation?

    Postorder visits operands first and the operator last, which is exactly reverse Polish notation.
  3. 3. What defines a prefix code?

    That property lets a bit stream be decoded uniquely without separators.
  4. 4. In Huffman's algorithm, which trees are merged at each step?

    Merging the two lowest-weight trees pushes the rarest symbols deepest, giving them the longest codes.

Summary

  • Preorder, inorder and postorder differ in when the node is visited; level order uses a queue.
  • Inorder of a search tree is sorted; postorder of an expression tree is postfix notation and gives a natural evaluation order.
  • A prefix code has no codeword that starts another, so it is a binary tree with symbols at leaves.
  • Huffman's algorithm repeatedly merges the two lightest trees with a priority queue and gives an optimal prefix code.

Continue with Trees and Spanning Trees for minimum spanning trees, or move on to Eulerian and Hamiltonian Paths.