Chapter 7: Trees
The introduction places trees within graphs and shows why specialized trees matter for compression and database storage.
After this chapter you will be able to
- Trees within graphs. Explain that trees are a subset of graphs and that their many specialized types make them worth studying separately.
- Rooted tree structure. Explain that a tree is a graph made of nodes and edges, and that this chapter uses rooted trees, in which one node leads to all the others.
- Tree node relationships. Distinguish parents, children, the root, and leaf nodes by their relationships to other nodes.
- Directory Tree Traversal. Describe how breadth-first search visits a directory and its subdirectories to print every file name.
- No Revisited Folders in Trees. Explain why this directory-tree traversal does not need to record which folders have already been searched, and how symbolic links change that assumption.
- Directory traversal order. Explain how breadth-first and depth-first search handle folders differently and why they print the same file names in different orders.
- Closest match search. Justify why breadth-first search, but not depth-first search, finds the closest mango seller in the social-network example.
- Tree definition and scope. State that a tree is a connected, acyclic graph and that the trees discussed in this chapter also have a root. Explain that the key restriction to remember is that trees cannot have cycles.
- Binary tree structure. Explain that a binary tree is a tree in which each node has at most two children, traditionally called the left child and right child. Describe how people may refer to the left and right subtrees, and note that the nodes’ data need not be related as it is in an ancestry tree.
- Frequency based code lengths. Explain how Huffman coding saves space by giving characters codes of different lengths, with shorter codes for characters that occur more often.
- Tree path coding and decoding. Trace how a character’s code is read from the Huffman tree and how a stream of variable-length codes is decoded.
- Tree properties for unambiguous codes. Justify why placing letters at leaves of a rooted binary tree avoids overlapping codes and supports decoding.
- Trees and binary trees. Explain that a tree is a graph without cycles and that a binary tree is a tree whose nodes have at most two children.
- Depth-first search limitation. Describe depth-first search as a graph traversal algorithm and state its limitation for finding shortest paths.
What it builds on
- What is a graph? (chapter 6) · The earlier introduction to what a graph is.
- Breadth-first search (chapter 6) · Introduces breadth-first search as a graph algorithm.
- Queues (chapter 6) · Introduces the queue used to track what remains to be searched.
- Implementing the algorithm (chapter 6) · The earlier breadth-first search kept track of already-searched people.
- Finding the shortest path (chapter 6) · Finding a shortest path with breadth-first search.
Section by section
Introduction
The introduction places trees within graphs and shows why specialized trees matter for compression and database storage.
- Trees within graphs: Explain that trees are a subset of graphs and that their many specialized types make them worth studying separately.
Why it matters: This connects the chapter’s subject to graphs while explaining why trees get their own treatment. - Trees behind practical applications: Describe the introduction’s examples of trees underlying compression and database storage: Huffman coding uses binary trees, and most databases use a balanced tree like a B-tree.
Why it matters: These examples show that trees are useful in more than one kind of computing task.
Key terms: trees, graphs, specialized types of trees, Huffman coding, binary trees, balanced tree, B-tree
7.1 Your first tree
Introduces rooted trees as graphs and defines the node relationships used throughout the chapter.
- Rooted tree structure: Explain that a tree is a graph made of nodes and edges, and that this chapter uses rooted trees, in which one node leads to all the others.
Why it matters: This establishes what the chapter means by a tree. - Tree node relationships: Distinguish parents, children, the root, and leaf nodes by their relationships to other nodes.
Why it matters: These terms let you describe where nodes sit in a tree.
Key terms: tree, graph, nodes, edges, rooted trees, parent, child, root, leaf nodes
7.2 File Directories
The section uses breadth-first search to list files in a directory tree and explains why a tree needs no visited-folder tracking.
- Directory Tree Traversal: Describe how breadth-first search visits a directory and its subdirectories to print every file name.
Why it matters: This shows how a graph algorithm can solve the practical task of listing files, including those in subdirectories. - No Revisited Folders in Trees: Explain why this directory-tree traversal does not need to record which folders have already been searched, and how symbolic links change that assumption.
Why it matters: The no-cycles property explains why this version of the search is simpler than the earlier graph search.
Key terms: breadth-first search, traversal algorithm, queue, node, trees, cycles, parent, symbolic links
7.3 A space odyssey: Depth-first search
The section contrasts depth-first and breadth-first traversal of a file directory, then explains why only breadth-first search finds the closest match in the examples.
- Directory traversal order: Explain how breadth-first and depth-first search handle folders differently and why they print the same file names in different orders.
Why it matters: The order in which an algorithm explores folders changes the order in which it finds their files. - Closest match search: Justify why breadth-first search, but not depth-first search, finds the closest mango seller in the social-network example.
Why it matters: Finding a match is not enough when the task requires the closest match.
Key terms: breadth-first search, depth-first search, queue, recursively, shortest path, first-degree friends
7.4 A better definition of trees
Defines a tree as a connected graph without cycles and clarifies that the chapter considers rooted trees.
- Tree definition and scope: State that a tree is a connected, acyclic graph and that the trees discussed in this chapter also have a root. Explain that the key restriction to remember is that trees cannot have cycles.
Why it matters: This definition gives you a way to recognize the trees used in the rest of the chapter.
Key terms: tree, connected, acyclic graph, rooted trees, root, cycles
7.5 Binary trees
Defines binary trees by their limit of two children per node and introduces left and right children and subtrees.
- Binary tree structure: Explain that a binary tree is a tree in which each node has at most two children, traditionally called the left child and right child. Describe how people may refer to the left and right subtrees, and note that the nodes’ data need not be related as it is in an ancestry tree.
Why it matters: This definition lets you recognize binary trees even when their data looks nothing like a family tree.
Key terms: binary tree, node, left child, right child, left subtree, right subtree
7.6 Huffman coding
The section uses Huffman coding to show how a binary tree gives frequently used characters shorter codes while still allowing the encoded text to be decoded unambiguously.
- Fixed width character storage: Explain why a character in the section’s ISO-8859-1 example takes 8 bits and how that provides a baseline for compression.
Why it matters: The fixed-width example makes the space savings from shorter codes easier to see. - Character encoding alternatives: Distinguish the fixed-width ISO-8859-1 example from UTF-8 and explain why the section mentions different character encodings.
Why it matters: It prevents the simple one-byte example from being mistaken for a rule about all text. - Frequency based code lengths: Explain how Huffman coding saves space by giving characters codes of different lengths, with shorter codes for characters that occur more often.
Why it matters: This is the central reason the section’s Huffman example compresses text. - Tree path coding and decoding: Trace how a character’s code is read from the Huffman tree and how a stream of variable-length codes is decoded.
Why it matters: Following the tree replaces fixed-size chunking when character codes have different lengths. - Tree properties for unambiguous codes: Justify why placing letters at leaves of a rooted binary tree avoids overlapping codes and supports decoding.
Why it matters: These properties explain why variable-length codes can still be read without confusing one letter with another.
Key terms: bit, byte, ISO-8859-1, ASCII, Unicode, UTF-8, variable-length character encoding, Huffman coding, compression, shorter codes
7.7 Recap
Recaps how trees and binary trees relate to graphs, what depth-first search cannot do, and how Unicode and UTF-8 relate to character encoding.
- Trees and binary trees: Explain that a tree is a graph without cycles and that a binary tree is a tree whose nodes have at most two children.
Why it matters: These distinctions help you recognize what makes a graph a tree and what makes a tree binary. - Depth-first search limitation: Describe depth-first search as a graph traversal algorithm and state its limitation for finding shortest paths.
Why it matters: Traversing a graph and finding a shortest path are different tasks. - Unicode and UTF-8 distinction: Distinguish Unicode from UTF-8 using the recap’s description of each.
Why it matters: The distinction keeps the international standard separate from its most common encoding.
Key terms: tree, graph, cycles, binary tree, children, depth-first search, graph traversal algorithm, shortest paths, character encodings, Unicode
Where this is used later
- B-trees (chapter 8) · The section examines the named database-tree type, B-trees.
- Min heaps and priority queues (chapter 13) · The idea of a tree-based data structure.
- (chapter intro) (chapter 8) · The reader has encountered binary trees.
- Improving insertion speed with trees (chapter 8) · The binary-tree structure of nodes and children
- Shorter trees are faster (chapter 8) · The binary tree structure in which searches move between nodes.
- A balancing act (chapter 8) · The discussion of balanced trees builds on the basic idea of a tree.
Concepts explained in this chapter
- treeA tree is a connected graph with no cycles, so no path of edges leads back to an earlier vertex.
- binary treeA binary tree is a tree in which each node has at most two children.
- rooted treeA rooted tree is a tree with one distinguished root node from which traversal begins.
- Huffman encodingHuffman coding is a lossless compression algorithm that represents more frequent symbols with shorter variable-length codes.
- leaf nodeA leaf node is a node in a tree that has no children.
- UTF-8UTF-8 is a variable-length character encoding for representing Unicode text using one to four bytes per character.
- UnicodeUnicode is a character encoding standard that assigns code points to characters across writing systems.
- encodingA character encoding is a system that represents text characters as binary code values.
- breadth-first searchBreadth-first search is a graph-search algorithm that explores vertices in increasing order of their distance from a starting vertex.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.