Deleting from a binary search tree, traversals, uses of trees and general trees

Overview

Recall questions on deleting leaf, one-child and two-children nodes from a binary search tree, in-order successors and predecessors, pre-order, in-order, post-order and breadth-first traversals, uses of trees, and adding nodes to a general tree.

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

   How do you delete a leaf node from a binary search tree?

   Model answer

   This is the easy case. Find the node and its parent, then set the parent's pointer that referred to it - the left one or the right one, whichever it was - to null, and release the node. Nothing else in the tree is affected, because a leaf has no descendants that need rehoming.

2. 2

   How do you delete a node that has exactly one child?

   Model answer

   The child, together with its whole subtree, takes the deleted node's place. Set the parent's pointer that referred to the deleted node to point instead at that single child, then release the node. The ordering rule still holds, because everything in that subtree was already on the correct side of the parent. If the node being deleted is the root, you set the root pointer to the child instead.

3. 3

   How do you delete a node that has two children?

   Model answer

   You cannot simply remove it, because both subtrees would be cut loose. Instead: find the in-order successor of the node - the smallest value in its right subtree, reached by moving once to the right and then as far left as possible. Copy that successor's value into the node being deleted, so the node keeps its position and pointers but now holds the correct replacement value. Then delete the successor node from its original place, which is straightforward because the leftmost node of a subtree has no left child, so it is either a leaf or has one right child only. The ordering rule is preserved because the successor is the very next value in sorted order, so everything in the left subtree is still smaller and everything remaining in the right subtree is still larger.

4. 4

   Delete the root 50 from the tree built from 50, 30, 70, 20, 40, 60, 80. Describe the result.

   Model answer

   50 has two children, so find its in-order successor: go right to 70, then as far left as possible, reaching 60, which has no left child. Copy 60 into the root, so the root now holds 60. Then delete the original 60 node, which is a leaf, by setting 70's left pointer to null. The tree is now: root 60, with left child 30 (whose children are 20 and 40) and right child 70 (whose only child is 80, on the right). An in-order traversal gives 20, 30, 40, 60, 70, 80, still in ascending order, which confirms the tree is valid.

5. 5

   The in-order predecessor can be used instead of the successor when deleting a node with two children. What is it, and why does it work equally well?

   Model answer

   The in-order predecessor is the largest value in the node's left subtree, reached by moving once to the left and then as far right as possible. It works for the same reason as the successor: it is the value immediately before the deleted one in sorted order, so putting it in the deleted node's place leaves everything in the left subtree smaller and everything in the right subtree larger. Like the successor, it can have at most one child, so removing it from its old position is a simple case. Either choice is correct; implementations just have to pick one and be consistent.

6. 6

   Define the pre-order, in-order and post-order traversals of a binary tree.

   Model answer

   All three are recursive and differ only in when the current node is processed. Pre-order: visit the node, then traverse the left subtree, then the right subtree. In-order: traverse the left subtree, then visit the node, then traverse the right subtree. Post-order: traverse the left subtree, then the right subtree, then visit the node. The word before 'order' tells you where the node itself comes.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.