Rooted tree

As explained in Grokking Algorithms, Second Edition

A rooted tree is a tree with one distinguished root node from which traversal begins.

A rooted tree is a connected, acyclic graph with one distinguished root node. Traversal begins at the root, which leads to the other nodes. Every node can have children and at most one parent; the only node without a parent is the root. section 7.1 section 7.4

The basic vocabulary is straightforward:

• A leaf node has no children. section 7.1
• A tree cannot contain cycles, so following its paths cannot trap you in an infinite loop. section 7.4 section 7.6
• Unlike a general graph, a rooted tree provides a definite starting point. section 7.6

Huffman coding

Huffman coding uses a rooted binary tree: letters appear at leaf nodes, and each letter has one unique path from the root. Reading path digits eventually reaches a letter because the tree has no cycles. A binary tree allows at most two children, conventionally a left and a right child, matching the two possible digits. section 7.6

Use the accompanying figure to identify the root, parent and child relationships, and leaf nodes. section 7.1

How Grokking Algorithms, Second Edition covers it

How deep it goes

Defines rooted trees through nodes, edges, parent-child relationships, connectedness, and acyclicity, then applies them to binary coding.

Examples

Uses terminology diagrams and Huffman coding paths from roots to letter-bearing leaves as concrete examples.

What you can do after

Evaluate/understand rooted-tree structure and follow unique paths from a root to leaves in binary coding.

How it connects

Connects rooted trees with graphs, nodes, edges, parent-child relationships, leaf nodes, binary trees, and Huffman coding.

liveBookmanning.com

Read Grokking Algorithms, Second Edition on liveBook Get the book at manning.com

Related concepts

• treekind of · A tree is a connected, acyclic structure of nodes, commonly organized hierarchically through parent-child relationships and optionally around a designated root.
• leaf nodehas part · A leaf node is a node in a tree or hierarchical structure that has no child nodes and cannot be further subdivided.
• root nodehas part · A root node is the designated starting node of a rooted tree or hierarchy, with no parent within that structure.

This explainer was generated by Manning's knowledge graph from the text of Grokking Algorithms, Second Edition. The section links point to the parts of the book it draws on.