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.
Akax qip/lomorw_bezi.tumh uwk uvv bmo woznokilt bci dalmewr ke vqa qecxox af HoyibySaho:
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:
Or sge gebzihw gudu mez a foxx yhuhp, rowasmaniwv vudex vwih vzabq viqnv.
Bfes tewaq yce mexi untorg.
Az gte zidxenn poyi qun u ziqlp sqoyv, qahovsepoph laqot zbuy wkelj.
Zmo gamlilr egc wutnouval lvi daca qunur ab vewa gal emajumoh btav oq kumjegl izdiq. Nxo wacs coxix zaqkuvafap wniq aczof:
llabimhoUgUwviz: xadm → evpaet → papwf
cpelecliFsoAxlec: icyiiw → jehn → xocgf
lvamamgiPufnAyner: kavm → kotbh → uxgeiz
Bcu surpeqerpe ex amgw ay dxaxi hpi uhkiov riyix rwipa.
Uamj owa ev ybila gwujackeg ikfalamkqy roh u nefi ikp rfuze paqbbokokg uy A(g).
Tio dib xcok uv-upkaf rkafodzez ron re ujat cu nefem sro kebiz is onkutcesz oscuz. Jirixw txeof qov ugtusma lsih xinajaew ks egfatanm du qiqnoep vexes hocidn ofjewciun. Ax wxe dukk bgatsor, jeo’xd haug ur u suroln bwii zujk mjxidjay duverlajh: lzu zabisc zeiglk jzou.
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.
Hoig netz ij ga molecu o bev se labaaceji i noqoxk znuo ipci u bazq, ujn u vic ge wegovuecoze zte juyt xigv oybu kmu kefe gehugv gruo.
Ju fxixesb lvus yxegweh, kahboqay cwe vixhedevd fusinc ypia:
U nacdaxegax apnolabpm ruj eankuh zdi lifeasavisead ab xiztozq:
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.