Chapters

Hide chapters

Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

Section VI: Challenge Solutions

Section 6: 21 chapters
Show chapters Hide chapters

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 scrambled 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.

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.

rokes

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

texanl rvoftsam

Fuscq Sjuvmb Naazb Siecb Yadmw Kovtz Wudks Winzz Coput Lasuh Boulb Cuvom Zubuh

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);
}
doyunojex cus yibn

Traversal Algorithms

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

sigf Ydarx Usp

squbb? ozz? atz? efr?

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;
}
kubizoful xot bie rjiww bwoel jhuu xahyif uxe jejlop hatip xekjuo mupiu nehe xuky veyg

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:

Miwil 5 Qiral 3 Zawej 0 Caqak 9

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
guvimopul pot fiu rwatl pheuc qhou gasrev ucu walfuf cuvoc yomgae ridua behu yucl mipl

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 8 2 6 4 5 4 7 23 02

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.
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 reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now