跳转至

8 Binary Trees

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:

parentleft childright 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:

710589

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.

Open lib/binary_node.dart and add the following two methods to the bottom of BinaryNode:

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

This will recursively create a string representing the binary tree.

Note

This algorithm is based on an implementation by Károly Lőrentey in his book Optimizing Collections, available from https://www.objc.io/books/optimizing-collections/.

Try it out by opening bin/starter.dart and running the following in main:

final tree = createBinaryTree();
print(tree);

You should see the following console output:

 ┌── null
┌──9
│ └── 8
7
│ ┌── 5
└──1
 └── 0

You’ll use this method of diagraming for other binary trees in this book.

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:

  1. If the current node has a left child, recursively visit this child first.
  2. Then visit the node itself.
  3. If the current node has a right child, recursively visit this child.

Here’s what an in-order traversal looks like for your example tree:

7105891058790, 1, 5, 7, 8, 9

You may have noticed that this prints the example tree in ascending order. If the tree nodes are structured in a certain way, in-order traversal visits them in ascending order! Binary search trees take advantage of this, and you’ll learn more about them in the next chapter.

Add the following code to BinaryNode in lib/binary_node.dart:

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

Following the rules laid out above, you first traverse to the left-most node before visiting the value. You then traverse to the right-most node.

Head back to main and replace its content to test this out:

final tree = createBinaryTree();
tree.traverseInOrder(print);

Run that and you should see the following in the console:

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:

9871058905717, 1, 0, 5, 9, 8

Write the following to BinaryNode just below your in-order traversal method:

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

You call action before recursively traversing the children, hence the “pre” of pre-order traversal.

Test it out back in main with the following code:

final tree = createBinaryTree();
tree.traversePreOrder(print);

You should see the following output in the console:

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.

7105890587190, 5, 1, 8, 9, 7

In other words, given any node, you’ll visit its children before visiting itself. An interesting consequence of this is that the root node is always visited last.

Back inside BinaryNode, write the following below traversePreOrder:

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

Note that you perform action after the recursive traversal calls.

Go back to main to try it out:

final tree = createBinaryTree();
tree.traversePostOrder(print);

You should see the following in the console:

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

The methods all contained the same lines of code but executed them in varying order. The list below summarizes that order:

  • traverseInOrder: left → action → right
  • traversePreOrder: action → left → right
  • traversePostOrder: left → right → action

The difference is only in where the action takes place.

Each one of these traversal algorithms has a time and space complexity of O(n).

You saw that in-order traversal can be used to visit the nodes in ascending order. Binary trees can enforce this behavior by adhering to certain rules during insertion. In the next chapter, you’ll look at a binary tree with stricter semantics: the binary search tree.

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.

Your task is to devise a way to serialize a binary tree into a list, and a way to deserialize the list back into the same binary tree.

To clarify this problem, consider the following binary tree:

15512171025

A particular algorithm may output the serialization as follows:

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

The deserialization process should transform the list back into the same binary tree. Note that there are many ways to perform serialization. You may choose any way you wish.

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.