9.
Binary Trees
Written by Jonathan Sande
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as 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:
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:
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:
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:
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.
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.
[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 child and right child.
- 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 node.