Binary Trees and the Binary Search Tree

Lesson 6 of 17 · Graphs and trees

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:

TraversalOrderFor the tree from the picture
preorder (before)vertex, left, right1 2 4 5 3 6
inorder (between)left, vertex, right4 2 5 1 3 6
postorder (after)left, right, vertex4 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.

Inserting in order: 8 3 10 1 6 14 4

          8
        /   \
       3     10
      / \      \
     1   6      14
        /
       4
#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
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
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?