In a binary tree every vertex has at most two children – a left and a right one. Three classic traversals are defined on such a tree, and a binary search tree (BST) stores numbers so that searching works like binary search.
Before you start: prerequisites – trees, recursion. How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.
Representing a binary tree
1
/ \
2 3
/ \ \
4 5 6
The simplest way is to keep two arrays: L[v] (the left child) and R[v] (the right child), with 0 when there is no child. For the tree from the picture: L[1]=2, R[1]=3, L[2]=4, R[2]=5, L[3]=0, R[3]=6, and the vertices 4, 5 and 6 have no children.
Three traversals: preorder, inorder, postorder
The traversals differ only in when the vertex is printed relative to its subtrees:
Traversal
Order
For the tree from the picture
preorder (before)
vertex, left, right
1 2 4 5 3 6
inorder (between)
left, vertex, right
4 2 5 1 3 6
postorder (after)
left, right, vertex
4 5 2 6 3 1
#include <iostream>
using namespace std;
int L[1001], R[1001];
void preorder(int v) {
if (v == 0) return; // there is no vertex
cout << v << " ";
preorder(L[v]);
preorder(R[v]);
}
void inorder(int v) {
if (v == 0) return;
inorder(L[v]);
cout << v << " ";
inorder(R[v]);
}
void postorder(int v) {
if (v == 0) return;
postorder(L[v]);
postorder(R[v]);
cout << v << " ";
}
int main() {
int n;
cin >> n; // vertices 1..n, the root is 1
for (int v = 1; v <= n; v++) cin >> L[v] >> R[v];
preorder(1); cout << endl;
inorder(1); cout << endl;
postorder(1); cout << endl;
return 0;
}
Example (the tree from the picture)
Input
6
2 3
4 5
0 6
0 0
0 0
0 0
Output
1 2 4 5 3 6
4 2 5 1 3 6
4 5 2 6 3 1
Postorder is used when the result for a vertex depends on its children (height, subtree size), and preorder when information is passed from the root towards the leaves (depth).
The height of a binary tree
The height of an empty tree is −1, and otherwise it is 1 + the larger of the heights of the left and right subtrees:
int height(int v) {
if (v == 0) return -1; // an empty tree
return 1 + max(height(L[v]), height(R[v]));
}
The binary search tree (BST)
In a BST the following holds for every vertex: all the values in the left subtree are smaller, and in the right one larger than the value of the vertex. Searching starts from the root: if the wanted number is smaller, we go left, if it is larger – right. Insertion goes along the same path until it reaches an empty place.
#include <iostream>
using namespace std;
const int MAXN = 100001;
int val[MAXN], L[MAXN], R[MAXN]; // the vertices are created in order 1, 2, 3, ...
int nodeCount = 0;
int insert(int v, int x) { // inserts x into the subtree of vertex v, returns the (new) root of the subtree
if (v == 0) { // an empty place: a new vertex
nodeCount++;
val[nodeCount] = x;
return nodeCount;
}
if (x < val[v]) L[v] = insert(L[v], x);
else if (x > val[v]) R[v] = insert(R[v], x);
return v; // equal values are not inserted again
}
bool find(int v, int x) {
while (v != 0) {
if (x == val[v]) return true;
v = (x < val[v]) ? L[v] : R[v];
}
return false;
}
void inorder(int v) {
if (v == 0) return;
inorder(L[v]);
cout << val[v] << " ";
inorder(R[v]);
}
int main() {
int n, root = 0;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
root = insert(root, x);
}
inorder(root); // prints the numbers sorted!
cout << endl;
cout << (find(root, 6) ? "6 exists" : "6 does not exist") << endl;
cout << (find(root, 7) ? "7 exists" : "7 does not exist") << endl;
return 0;
}
Example (the tree from the picture)
Input
7
8 3 10 1 6 14 4
Output
1 3 4 6 8 10 14
6 exists
7 does not exist
An inorder traversal of a BST gives the values sorted – that is also the way to check whether a tree is a correct BST.
Complexity and balanced trees
Searching and insertion take as many steps as the height of the tree. If the numbers were inserted in random order, the height is about log₂ n. But if they are inserted already sorted (1, 2, 3, …), the tree becomes a chain of height n and all the operations are O(n).
Balanced trees (red-black, AVL) rearrange themselves so that the height stays O(log n). They do not need to be written by hand: C++ set and map are exactly balanced binary search trees.
Practice tasks
Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.
TASK 01Difficulty: medium
Is the tree a BST?
A binary tree with n vertices is given (the root is 1). For every vertex its value and children L R (0 if there is none) are given. Print YES if the tree is a binary search tree (all the values are different), and NO otherwise.
Input: n, then for every vertex value L R.
Example 1
Input
5
8 2 3
3 4 5
10 0 0
1 0 0
6 0 0
Output
YES
Example 2
Input
3
5 2 3
3 0 0
4 0 0
Output
NO
Hint
It is not enough to compare a vertex only with its children. The easiest way: do an inorder traversal and check whether the resulting sequence is strictly increasing.
Solution (C++)
#include <iostream>
#include <vector>
using namespace std;
int val[100001], L[100001], R[100001];
vector<int> order;
void inorder(int v) {
if (v == 0) return;
inorder(L[v]);
order.push_back(val[v]);
inorder(R[v]);
}
int main() {
int n;
cin >> n;
for (int v = 1; v <= n; v++) cin >> val[v] >> L[v] >> R[v];
inorder(1);
bool ok = true;
for (size_t i = 1; i < order.size(); i++)
if (order[i - 1] >= order[i]) ok = false; // it must be strictly increasing
cout << (ok ? "YES" : "NO") << endl;
return 0;
}
TASK 02Difficulty: easy
The height of a BST
Numbers are inserted in order into an empty binary search tree. Print the height of the resulting tree (a tree with one vertex has the height 0).
Example 1
Input
7
8 3 10 1 6 14 4
Output
3
Example 2
Input
4
1 2 3 4
Output
3
Hint
Use the function insert from the lesson and the recursive function height. The second example shows that a sorted input makes a chain.
Solution (C++)
#include <iostream>
#include <algorithm>
using namespace std;
int val[100001], L[100001], R[100001], nodeCount = 0;
int insert(int v, int x) {
if (v == 0) {
val[++nodeCount] = x;
return nodeCount;
}
if (x < val[v]) L[v] = insert(L[v], x);
else if (x > val[v]) R[v] = insert(R[v], x);
return v;
}
int height(int v) {
if (v == 0) return -1;
return 1 + max(height(L[v]), height(R[v]));
}
int main() {
int n, root = 0;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
root = insert(root, x);
}
cout << height(root) << endl;
return 0;
}
Common mistakes and tips
The base case of a traversal is "there is no vertex" (v == 0), not "a leaf".
When checking a BST it is not enough that the left child is smaller than the parent – the whole left part must be smaller.
A sorted input makes a BST chain; then the recursion is n deep and the operations are O(n). For a guaranteed O(log n) use set.
Check your knowledge
Open the quiz
Binary trees
1. Which traversal of a BST gives the values sorted?
2. The order "vertex, left, right" is:
3. How many steps does searching take in a BST created by inserting the numbers 1, 2, …, n in order?
Podešavanja kolačića
Koristimo kolačiće da bismo vam pružili najbolje moguće iskustvo. Takođe nam omogućavaju da analiziramo ponašanje korisnika kako bismo stalno poboljšavali veb lokaciju za vas.