Trees: Hierarchy Everywhere

Цели урока

• Understand what a tree is and where it appears
• Learn the terminology: root, leaf, height, depth
• Understand binary trees
• Implement a tree node

Предварительные знания

• Linked lists

• Linked Lists

Open Windows Explorer or Finder on a Mac. Folders inside folders - that's a tree! Now imagine needing to find a file among a million. Tree structure makes that possible.

• File systems - folders and files
• HTML DOM - structure of web pages
• Databases - B-trees for indexes
• Compilers - AST (Abstract Syntax Tree)

Where trees and their vocabulary came from

The words we use for trees (root, parent, child, leaf, ancestor, descendant) come from genealogy and organisation charts, where people had drawn family lines that way for centuries. Trees showed up early in computing: expression parsers built parse trees, and Stephen Kleene leaned on tree structure in the 1950s while working on regular events and automata. The strict formalisation arrived with Donald Knuth in volume one of The Art of Computer Programming in 1968, where he carefully separated ordered from unordered trees and rooted trees (with a distinguished root) from free trees (with none). It is Knuth's framing, in which a subtree is itself a tree, that underpins the recursive definition this lesson uses.

Trees All Around Us

A **tree** is a hierarchical structure with a single root and branches to its children.

• File system - folders and files
• HTML DOM - tags nested inside each other
• Org chart - CEO → directors → managers → employees
• Family tree - ancestors and descendants

Unlike a graph, a tree has **no cycles** - the path from the root to any node is unique.

Terminology: Root, Leaf, Height

• **Root** - the top node, has no parent
• **Leaf** - a node with no children
• **Internal node** - a node with at least one child
• **Parent/Child** - a node and its direct descendant
• **Siblings** - children of the same parent
• **Depth** - distance from the root (root depth = 0)
• **Height** - maximum depth in the tree

Binary Tree

A **binary tree** - each node has **at most 2 children**: left and right.

**Types of binary trees:**

• **Full** - every node has either 0 or 2 children
• **Complete** - all levels are filled, the last level is filled left to right
• **Perfect** - all leaves are at the same depth, all internal nodes have 2 children
• **Balanced** - the heights of the left and right subtrees differ by at most 1

Tree Node Implementation

**Recursive structure:** a tree consists of a root + left subtree + right subtree. Each subtree is also a tree!

Binary Tree Properties

Useful formulas for binary trees:

• **Maximum nodes at level k:** 2^k
• **Maximum nodes in a tree of height h:** 2^(h+1) - 1
• **Minimum height for n nodes:** floor(log2(n))

Key Concepts

• Tree = hierarchy without cycles
• Root - the top node, Leaf - a node with no children, Height - max depth
• Binary tree: at most 2 children per node
• Node: val + left + right
• Trees are recursive: a subtree is also a tree

Next

How to visit all nodes in a tree? Three classic traversals (inorder, preorder, postorder) - in the next lesson!

• Tree Traversals — How to visit all nodes
• Binary Search Tree — A tree for fast lookups

Связанные уроки

• ds-02-linked-lists — Trees generalise linked lists to multiple children
• ds-10-tree-traversals — Traversal algorithms operate on the tree structure introduced here
• ds-11-bst — BST adds an ordering invariant on top of tree structure
• ds-16-graphs-intro — Trees are a special case of DAGs, which are a special case of graphs
• comp-16-ast
• plt-26-ast