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

8. Binary Trees
Written by Kelvin Lau & Jonathan Sande

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

In the previous chapter, you looked at a basic tree where each node can have many children. A binary tree is a tree where each node has at most two children, often referred to as the left and right children:

parent left child right child

Binary trees serve as the basis for many tree structures and algorithms. In this chapter, you’ll build a binary tree and learn about the three most important tree traversal algorithms.

Implementation

Create a folder called lib in the root of your starter project and in that folder create a file named binary_node.dart. Then add the following code:

class BinaryNode<T> {
  BinaryNode(this.value);
  T value;
  BinaryNode<T>? leftChild;
  BinaryNode<T>? rightChild;
}

Rather than maintaining a list of child nodes as you did with TreeNode in the previous chapter, you can directly reference leftChild and rightChild. They’re nullable since not every node will have children.

Now open bin/starter.dart and import your new class:

import 'package:starter/binary_node.dart';

Add the following top-level function below main:

BinaryNode<int> createBinaryTree() {
  final zero = BinaryNode(0);
  final one = BinaryNode(1);
  final five = BinaryNode(5);
  final seven = BinaryNode(7);
  final eight = BinaryNode(8);
  final nine = BinaryNode(9);

  seven.leftChild = one;
  one.leftChild = zero;
  one.rightChild = five;
  seven.rightChild = nine;
  nine.leftChild = eight;

  return seven;
}

This defines the following tree:

7 1 0 5 8 9

Building a Diagram

Building a mental model of a data structure can be quite helpful in learning how it works. To that end, you’ll implement a reusable algorithm that helps visualize a binary tree in the console.

@override
String toString() {
  return _diagram(this);
}

String _diagram(
  BinaryNode<T>? node, [
  String top = '',
  String root = '',
  String bottom = '',
]) {
  if (node == null) {
    return '$root null\n';
  }
  if (node.leftChild == null && node.rightChild == null) {
    return '$root ${node.value}\n';
  }
  final a = _diagram(
    node.rightChild,
    '$top ',
    '$top┌──',
    '$top│ ',
  );
  final b = '$root${node.value}\n';
  final c = _diagram(
    node.leftChild,
    '$bottom│ ',
    '$bottom└──',
    '$bottom ',
  );
  return '$a$b$c';
}
final tree = createBinaryTree();
print(tree);
 ┌── null
┌──9
│ └── 8
7
│ ┌── 5
└──1
 └── 0

Traversal Algorithms

Previously, you looked at a level-order traversal of a tree. With a few tweaks, you could make that algorithm work for binary trees as well. However, instead of re-implementing level-order traversal, you’ll look at three traversal algorithms for binary trees: in-order, pre-order and post-order traversals.

In-Order Traversal

An in-order traversal visits the nodes of a binary tree in the following order, starting from the root node:

6 9 3 2 5 9 0 9 4 0 4 8
8, 2, 0, 6, 1, 3

void traverseInOrder(void Function(T value) action) {
  leftChild?.traverseInOrder(action);
  action(value);
  rightChild?.traverseInOrder(action);
}
final tree = createBinaryTree();
tree.traverseInOrder(print);
0
1
5
7
8
9

Pre-Order Traversal

Pre-order traversal always visits the current node first, then recursively visits the left and right child:

8 2 3 8 1 7 5 7 5 7 2 1
3, 7, 7, 4, 9, 9

void traversePreOrder(void Function(T value) action) {
  action(value);
  leftChild?.traversePreOrder(action);
  rightChild?.traversePreOrder(action);
}
final tree = createBinaryTree();
tree.traversePreOrder(print);
7
1
0
5
9
8

Post-Order Traversal

Post-order traversal only visits the current node after the left and right child have been visited recursively.

6 5 9 1 9 5 0 8 2 2 0 9
6, 8, 2, 8, 3, 7

void traversePostOrder(void Function(T value) action) {
  leftChild?.traversePostOrder(action);
  rightChild?.traversePostOrder(action);
  action(value);
}
final tree = createBinaryTree();
tree.traversePostOrder(print);
0
5
1
8
9
7

Comparison

Take a moment to review the differences between those three traversal algorithms:

void traverseInOrder(void Function(T value) action) {
  leftChild?.traverseInOrder(action);
  action(value);
  rightChild?.traverseInOrder(action);
}

void traversePreOrder(void Function(T value) action) {
  action(value);
  leftChild?.traversePreOrder(action);
  rightChild?.traversePreOrder(action);
}

void traversePostOrder(void Function(T value) action) {
  leftChild?.traversePostOrder(action);
  rightChild?.traversePostOrder(action);
  action(value);
}

Challenges

Binary trees are a surprisingly popular topic in algorithm interviews. Questions on the binary tree not only require a good foundation of how traversals work, but can also test your understanding of recursive backtracking, so it’s good to test what you’ve learned in this chapter.

Challenge 1: Height of a Tree

Given a binary tree, find the height of the tree. The height of the binary tree is determined by the distance between the root and the furthest leaf. The height of a binary tree with a single node is zero since the single node is both the root and the furthest leaf.

Challenge 2: Serialization

A common task in software development is representing a complex object using another data type. This process is known as serialization and allows custom types to be used in systems that only support a closed set of data types. An example of serialization is JSON.

27 4 99 84 07 83

[15, 10, 5, null, null, 12, null, null, 25, 17, null, null, null]

Key Points

  • A binary tree is a tree where each node has at most two children, often referred to as the left and right children.
  • Tree traversal algorithms visit each node in the tree once.
  • In-order traversal recursively visits the left child first, then the current parent node, and finally the right child.
  • Pre-order traversal visits the parent node first, followed by the child nodes.
  • Post-order traversal visits the child nodes before the parent nodes.
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