8.
Trees
Written by Jonathan Sande
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
The tree is a data structure of profound importance. It’s used to tackle many recurring challenges in software development, such as:
- Representing hierarchical relationships.
- Managing sorted data.
- Facilitating fast lookup operations.
There are many types of trees, and they come in various shapes and sizes. In this chapter, you’ll learn the basics of using and implementing a tree.
Terminology
Many terms are associated with trees, and here are some you should know right off the bat.
Node
Like the linked list, trees are made up of nodes.
Parent and Child
Trees are viewed starting from the top and branching towards the bottom, just like a real tree. Well, OK, exactly the opposite of a real tree. :]
Root
The topmost node in the tree is called the root of the tree. It is the only node that has no parent:
Leaf
A node is a leaf if it has no children:
Implementation
Since a tree is made up of nodes, your first task is to make a TreeNode class.
class TreeNode<T> {
TreeNode(this.value);
T value;
List<TreeNode<T>> children = [];
}
void add(TreeNode<T> child) {
children.add(child);
}
import 'package:starter/tree.dart';
void main() {
final beverages = TreeNode('Beverages');
final hot = TreeNode('Hot');
final cold = TreeNode('Cold');
beverages.add(hot);
beverages.add(cold);
}
Traversal Algorithms
Iterating through linear collections such as lists or linked lists is straightforward. Linear collections have a clear start and end:
Depth-First Traversal
Add the following method to TreeNode in lib/tree.dart:
void forEachDepthFirst(void Function(TreeNode<T> node) performAction) {
performAction(this);
for (final child in children) {
child.forEachDepthFirst(performAction);
}
}
TreeNode<String> makeBeverageTree() {
final tree = TreeNode('beverages');
final hot = TreeNode('hot');
final cold = TreeNode('cold');
final tea = TreeNode('tea');
final coffee = TreeNode('coffee');
final chocolate = TreeNode('cocoa');
final blackTea = TreeNode('black');
final greenTea = TreeNode('green');
final chaiTea = TreeNode('chai');
final soda = TreeNode('soda');
final milk = TreeNode('milk');
final gingerAle = TreeNode('ginger ale');
final bitterLemon = TreeNode('bitter lemon');
tree.add(hot);
tree.add(cold);
hot.add(tea);
hot.add(coffee);
hot.add(chocolate);
cold.add(soda);
cold.add(milk);
tea.add(blackTea);
tea.add(greenTea);
tea.add(chaiTea);
soda.add(gingerAle);
soda.add(bitterLemon);
return tree;
}
final tree = makeBeverageTree();
tree.forEachDepthFirst((node) => print(node.value));
beverages
hot
tea
black
green
chai
coffee
cocoa
cold
soda
ginger ale
bitter lemon
milk
Level-Order Traversal
A tree can be divided into levels based on the distance of the nodes from the root. The root itself is level 0, nodes that are direct children of the root are level 1, the children of these children are level 2, and on it goes. Here’s what that looks like in image form:
import 'queue.dart';
void forEachLevelOrder(void Function(TreeNode<T> node) performAction) {
final queue = QueueStack<TreeNode<T>>();
performAction(this);
children.forEach(queue.enqueue);
var node = queue.dequeue();
while (node != null) {
performAction(node);
node.children.forEach(queue.enqueue);
node = queue.dequeue();
}
}
final tree = makeBeverageTree();
tree.forEachLevelOrder((node) => print(node.value));
beverages
hot
cold
tea
coffee
cocoa
soda
milk
black
green
chai
ginger ale
bitter lemon
Search
You already have two methods that iterate through all the nodes, so building a search algorithm shouldn’t take long. Write the following at the bottom of TreeNode:
TreeNode<T>? search(T value) {
TreeNode<T>? result;
forEachLevelOrder((node) {
if (node.value == value) {
result = node;
}
});
return result;
}
final tree = makeBeverageTree();
final searchResult1 = tree.search('ginger ale');
print(searchResult1?.value); // ginger ale
final searchResult2 = tree.search('water');
print(searchResult2?.value); // null
Challenges
The following challenges will help to strengthen your understanding of the tree data structure. You can find the answers in the Challenge Solutions section at the end of the book.
Challenge 1: Print a Tree in Level Order
Print all the values in a tree in order based on their level. Nodes in the same level should be printed on the same line. For example, consider the following tree:
15
1 17 20
1 5 0 2 5 7
Challenge 2: Widget Tree
Flutter calls the nodes in its user-facing UI tree widgets. You can make a mini-version of the same thing.
Key Points
- Trees share some similarities to linked lists, but, whereas linked-list nodes may only link to one successor node, a tree node can connect to many child nodes.
- Every tree node, except for the root node, has exactly one parent node.
- A root node has no parent nodes.
- Leaf nodes have no child nodes.
- Visiting all the nodes of a tree is called traversal.
- In depth-first traversal, you start at the root and visit the first child of every node as far as you can before backtracking and going on to the child in another branch. You can accomplish this with recursion or a stack.
- In level-order traversal, you start at the root and visit all of its immediate children before going on to the next level of children. You can accomplish this with a queue.