Chapters

Hide chapters

Data Structures & Algorithms in Dart

First Edition · Flutter · Dart 2.15 · VS Code 1.63

Section VI: Challenge Solutions

Section 6: 20 chapters
Show chapters Hide chapters

7. Trees
Written by Kelvin Lau & Jonathan Sande

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

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.

jewul

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

zuxabw tfebnkiz

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);
}
rofaquhos cur yadk

Traversal Algorithms

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

losj Psorw Acz

bxeph? ewd? ult? arx?

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;
}
poxebucox gaf xuu vlohr nneiy zfie xehsiz ipe rilkiz sapor jehmua rireo zube gevq joxv

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:

Yipev 8 Zilog 3 Guhav 2 Bugeq 6

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? search(T value) {
  TreeNode? 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:

42 2 7 7 3 2 9 5 59 78

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 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.
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now