Trees and binary search trees: structure, insertion and searching

Overview

Recall questions on tree terminology, binary trees and the binary search tree rule, how a tree is stored and created, inserting and searching for values with traces, search efficiency, and the effect of inserting sorted data.

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

   What is a tree, and what do the terms root, child, parent, leaf and subtree mean?

   Model answer

   A tree is a connected graph with no cycles, usually drawn with a single root node at the top from which all others descend. A parent is a node with nodes directly beneath it; those nodes are its children. The root is the only node with no parent. A leaf (or terminal node) is a node with no children. A subtree is any node together with all of its descendants, considered as a tree in its own right. The connections are called edges or branches.

2. 2

   What makes a tree binary?

   Model answer

   Each node has at most two children, conventionally called the left child and the right child. A node may have two children, one child (either side) or none. The restriction is what makes the structure predictable enough to store with just two pointers per node and to search efficiently.

3. 3

   State the rule that makes a binary tree a binary search tree.

   Model answer

   For every node, all the values in its left subtree are less than the value at that node, and all the values in its right subtree are greater than it. The rule must hold at every node, not just at the root - it is not enough for a node's immediate children to be on the correct sides. Duplicate values are usually either disallowed or sent consistently to one side.

4. 4

   How is a binary search tree stored in memory?

   Model answer

   As a set of nodes, each holding the data item plus a left pointer and a right pointer, with a null pointer where a child is absent, and a separate root pointer identifying the first node. In a procedural, array-based implementation this becomes an array of records with three fields - data, left index and right index - where a value such as -1 stands for null; the object-oriented alternative is a Node class holding the data and two object references. Either approach is acceptable.

5. 5

   How do you create an empty binary search tree?

   Model answer

   Set the root pointer to null, meaning there is no first node yet. In an array-based version you also allocate the array of node records and build a free list of unused slots so that new nodes can be found. The first item inserted becomes the root, and the root pointer is set to it.

6. 6

   Describe the procedure for inserting a value into a binary search tree.

   Model answer

   If the root pointer is null, the new value becomes the root and you are finished. Otherwise start at the root and repeat: compare the new value with the current node's value; if it is smaller move to the left child, if larger move to the right child. When the pointer you would follow is null, that is where the new node belongs, so create the node with two null pointers and set that pointer to it. The new node is always inserted as a leaf, and no existing node ever moves.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.