Trees and binary search trees

Overview

Recall questions on rooted trees and their terms, the binary search tree rule, adding values, how insertion order changes search cost, searching with comparison counts, time complexity, finding the smallest value, uses of trees and expression trees.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   Describe the structure of a rooted tree.

   Model answer

   A tree is a connected structure of nodes joined by edges with no cycles. One node is designated the root and sits at the top. Every other node has exactly one parent above it and any number of children below it. A node with no children is a leaf, and any node together with everything below it forms a subtree.

2. 2

   Define these tree terms: root, child, parent, leaf, subtree.

   Model answer

   The root is the single node with no parent, from which the whole tree hangs. A child is a node directly below and connected to a given node; that given node is its parent. A leaf is a node with no children. A subtree is a node together with all of its descendants, and it is itself a valid tree.

3. 3

   Why does the shape of a binary search tree, rather than the number of nodes it holds, determine the cost of searching it?

   Model answer

   Because a search follows one path from the root downwards, comparing once per level, so the number of comparisons is the depth of the tree rather than its size. A balanced tree of n nodes has a depth of about log₂n, so a thousand nodes cost about ten comparisons and a million cost about twenty. A degenerate tree built by inserting values in sorted order has a depth of n, so a thousand nodes cost up to a thousand comparisons. Both trees hold identical data and support identical operations; only the shape differs, and the shape is decided by the order the values were inserted in.

4. 4

   What extra rule does a binary search tree obey?

   Model answer

   For every node, every value in its left subtree is less than that node's value, and every value in its right subtree is greater than it. The rule applies at every node, not just the root, which is what allows searching to discard a whole subtree at each step, and close to half of what remains while the tree stays balanced.

5. 5

   Describe the algorithm for adding a value to a binary search tree.

   Model answer

   If the tree is empty, the new value becomes the root. Otherwise start at the root and compare the new value with the current node: if it is smaller move to the left child, if larger move to the right child. Repeat until the required child position is empty, and place the new node there as a leaf. Duplicates are either rejected or handled by a stated convention.

6. 6

   The same seven values are inserted into a binary search tree in two different orders: 50, 30, 70, 20, 40, 60, 80 and then 20, 30, 40, 50, 60, 70, 80. How does the search cost differ?

   Model answer

   The first order gives a balanced tree of three levels: 50 at the root, 30 and 70 below it, and 20, 40, 60 and 80 as leaves. A search compares at most three values, and the cost is O(log n). The second order gives a degenerate tree: each value is larger than the one before, so every node becomes the right child of its predecessor and the tree is a straight line of seven levels. A search for 80 compares all seven values, and the cost is O(n) — no better than a linear search of a list, and with the memory overhead of the pointers on top. This is why the O(log n) figure quoted for a binary search tree holds only while the tree is reasonably balanced, and why self-balancing variants exist.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.