7 Trees¶

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.

A tree

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.

nodes

Each node can carry some data and keeps track of its children.

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. :]

Every node except for the topmost one is connected to exactly one node above it. That node is called a parent node. The nodes connected directly below a parent are called child nodes. In a tree, every child has exactly one parent. That’s what makes a tree a tree.

parentchildren

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:

You will run into more terms later on, but these should be enough to get you started.

Implementation¶

Since a tree is made up of nodes, your first task is to make a TreeNode class.

Open up the starter project for this chapter. Create a new file called tree.dart in the lib folder. Then add the following code to it:

class TreeNode<T> {
  TreeNode(this.value);
  T value;
  List<TreeNode<T>> children = [];
}

Like a linked-list node, each TreeNode stores a value. However, since tree nodes can point to multiple other nodes, you use a list to hold references to all the children.

Next, add the following method inside TreeNode:

void add(TreeNode<T> child) {
  children.add(child);
}

This method adds a child node to a node.

Time to give it a whirl. Open bin/starter.dart and replace the file contents with the following code::

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);
}

Hierarchical structures are natural candidates for tree structures, so here you’ve defined three different nodes and organized them into a logical hierarchy. This arrangement corresponds to the following structure:

beverageshotcold

Traversal Algorithms¶

Iterating through linear collections such as lists or linked lists is straightforward. Linear collections have a clear start and end:

nullStartEnd

Iterating through trees is a bit more complicated:

start?end?end?end?

Should nodes on the left have precedence? How should the depth of a node relate to its precedence? Your traversal strategy depends on the problem that you’re trying to solve. There are multiple strategies for different trees and different problems. In the next section, you’ll look at depth-first traversal, a technique that starts at the root and visits nodes as deep as it can before backtracking.

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);
  }
}

This deceptively simple code uses recursion to visit the next node. As you may recall from the previous chapter, recursive code is where a method calls itself. It’s particularly useful for visiting all of the members of a tree data structure.

This time you allow the caller to pass in an anonymous function named performAction that will be called once for every node. Then you visit all of the current node’s children and call their forEachDepthFirst methods. Eventually you reach leaf nodes without any children and so the recursive function calls don’t go on forever.

Note

It’s also possible to use a stack if you don’t want your implementation to be recursive. Recursion uses a stack under the hood.

Time to test it out. Add the following top-level function below main in bin/starter.dart:

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;
}

This function creates the following tree:

beverageshotteablackgreenchaiginger alebitter lemoncoffeecocoasodamilkcold

Replace the contents of main with the following:

final tree = makeBeverageTree();
tree.forEachDepthFirst((node) => print(node.value));

Running that produces the following depth-first output:

beverages
hot
tea
black
green
chai
coffee
cocoa
cold
soda
ginger ale
bitter lemon
milk

In the next section, you’ll look at level-order traversal, a technique that visits each node of the tree based on the depth of the nodes.

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:

Level 3Level 2Level 1Level 0

A level-order traversal means that you visit all of the nodes at an upper level before visiting any of the nodes at the next level down.

You can accomplish this by using a queue. The double-stack queue you made in Chapter 6 already exists in the lib folder of the starter project, so import it at the top of lib/tree.dart:

import 'queue.dart';

Then add the following method to TreeNode:

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();
  }
}

Note the following points:

The queue ensures that the nodes are visited in the right level-order. A simple recursion, which implicitly uses a stack, would not have worked!
QueueStack is one of the queue implementations you made in the last chapter. You could also use Queue from the dart:collection library, but you would need to adjust the code somewhat since the Dart Queue uses different method names.
You first enqueue the root node (level 0) and then add the children (level 1). The while loop subsequently enqueues all of the children on the next level down. Since a queue is first-in-first-out, this will result in each level dequeuing in order from top to bottom.

Head back to main and replace its content with the following:

final tree = makeBeverageTree();
tree.forEachLevelOrder((node) => print(node.value));

Run that and you should see the output below:

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? search(T value) {
  TreeNode? result;
  forEachLevelOrder((node) {
    if (node.value == value) {
      result = node;
    }
  });
  return result;
}

You iterate through each node and check if its value is the same as what you’re searching for. If so, you return it as the result, but return null if not.

Head back to main to test the code. Replace the function body with the following:

final tree = makeBeverageTree();

final searchResult1 = tree.search('ginger ale');
print(searchResult1?.value); // ginger ale

final searchResult2 = tree.search('water');
print(searchResult2?.value); // null

Run that and you’ll see the first search founds a match while the second doesn’t.

Here, you used your level-order traversal algorithm. Since it visits all of the nodes, if there are multiple matches, the last match will win. This means you’ll get different objects back depending on what traversal method you use.

This chapter was a general introduction to trees and tree traversal algorithms. In the next few chapters you’ll learn about more specialized types of trees.

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:

1552750111720

Your algorithm should print the following:

15
1 17 20
1 5 0 2 5 7

Flutter calls the nodes in its user-facing UI tree widgets. You can make a mini-version of the same thing.

Create three separate nodes with the following names and types:

Column: a tree node that takes multiple children.
Padding: a tree node that takes a single child.
Text: a tree leaf node.

Use your widget nodes to build a simple widget tree.

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 link 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.
Traversals, such as depth-first and level-order traversals, work on multiple types of trees. However, the implementation will be slightly different based on how the tree is structured.