2.7.3: Binary trees
- Page ID
- 10169
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Recursion is often used with linked data structures, which are data structures that are constructed by linking several objects of the same type together with pointers. For an example, we’ll look at the data structure known as a binary tree.
If you don’t already know about objects and pointers, you will not be able to able to follow the rest of this section. Time to read about it on the internet?
A binary tree consists of nodes linked together in a tree-like structure. The nodes can contain any type of data, but we will consider binary trees in which each node contains an integer. A binary tree can be empty, or it can consist of a node (called the root of the tree) and two smaller binary trees (called the left subtree and the right subtree of the tree). You can already see the recursive structure: a tree can contain smaller trees. In Java, the nodes of a tree can be represented by objects belonging to the class
class BinaryTreeNode { int item; // An integer value stored in the node. BinaryTreeNode left; // Pointer to left subtree. BinaryTreeNode right; // Pointer to right subtree. }
An empty tree is represented by a pointer that has the special value null. If root is a pointer to the root node of a tree, then root.left is a pointer to the left subtree and root.rightis a pointer to the right subtree. Of course, both root.left and root.right can be null if the corresponding subtree is empty. Similarly, root.item is a name for the integer in the root node.
BinarytreesarenotpartofthematerialforReasoning&Logicandonlyserve as examples of induction on algorithms here. You will study this material in more detail in the course Algorithms & Data Structures.
Let’s say that we want a function that will find the sum of all the integers in all the nodes of a binary tree. We can do this with a simple recursive function. The base case of the recursion is an empty tree. Since there are no integers in an empty tree, the sum of the integers in an empty tree is zero. For a non-empty tree, we can use recursion to find the sums of the integers in the left and right subtrees, and then add those sums to the integer in the root node of the tree. In Java, this can be expressed as follows:
int TreeSum( BinaryTreeNode root ) { // Find the sum of all the integers in the // tree that has the given root. int answer; if (root == null) { // The tree is empty. answer = 0; } else { answer = TreeSum(root.left); answer += TreeSum(root.right); answer += root.item; } return answer; }
We can use the second form of the principle of mathematical induction to prove that this function is correct.
Theorem 3.13.
The function TreeSum, defined above, correctly computes the sum of all the in- tegers in a binary tree.
Proof. We use induction on the number of nodes in the tree. Let P(n) be the statement “TreeSum correctly computes the sum of the nodes in any binary tree that contains exactly
n nodes”. We show that P(n) is true for every natural number n.
Consider the case n = 0. A tree with zero nodes is empty, and an empty tree is
represented by a null pointer. In this case, the if statement in the definition of TreeSum assigns the value 0 to the answer, and this is the correct sum for an empty tree. So, P(0)
is true.
Let k be an arbitrary natural number, with k > 0. Suppose we already know P(x)for each natural number x with 0 ≤ x < k. That is, TreeSum correctly computes the sum of all the integers in any tree that has fewer than k nodes. We must show that it follows that P(k) is true, that is, that TreeSum works for a tree with k nodes. Suppose that rootis a pointer to the root node of a tree that has a total of k nodes. Since the root node counts as a node, that leaves a total of k − 1 nodes for the left and right subtrees, so each subtree must contain fewer than k nodes. By the induction hypothesis, we know that TreeSum(root.left) correctly computes the sum of all the integers in the left subtree, and TreeSum(root.right) correctly computes the sum of all the integers in the right subtree. The sum of all the integers in the tree is root.item plus the sums of the integers in the subtrees, and this is the value computed by TreeSum. So, TreeSum does work for a tree with k nodes. This completes the induction.
Note how closely the structure of the inductive proof follows the structure of the recursive function. In particular, the second principle of mathematical induction is very natural here, since the size of subtree could be anything up to one less than the size of the complete tree. It would be very difficult to use the first principle of induction in a proof about binary trees.
Exercises
- The Hanoi subroutine given in this section does not just solve the Towers of Hanoi problem. It solves the problem using the minimum possible number of moves. Use induction to prove this fact.
- Use induction to prove that the Hanoi subroutine uses \(2^{n}-1\) moves to solve the Towers of Hanoi problem for n discs.
- Consider the following recursive function:
int power(int x, int n) { // Compute x raised to the power n. // Assume that n >= 0. int answer; if (n == 0) { answer = 1; } else if (n % 2 == 0) { answer = power(x * x, n / 2); } else { answer = x * power(x * x, (n-1) / 2); } return answer; }
Show that for any integer x and any non-negative integer n, the function power(x,n) correctly computes the value of \(x^{\prime \prime}\). (Assume that the int data type can represent arbitrarily large integers.) Note that the test “if (n % 2 == 0)” tests whether n is evenly divisible by 2. That is, the test is true if n is an even number. (This function is actually a very efficient way to compute \(x^{\prime \prime}\))
4. A leaf node in a binary tree is a node in which both the left and the right subtrees are empty. Prove that the following recursive function correctly counts the number of leaves in a binary tree:
int LeafCount(BinaryTreeNode root) { // Counts the number of leaf nodes in // the tree with the specified root. int count; if (root == null) { count = 0; } else if (root.left == null && root.right == null) { count = 1; } else{ count = LeafCount(root.left); count += LeafCount(root.right); } return count; }
5. A binary sort tree satisfies the following property: If node is a pointer to any node in the tree, then all the integers in the left subtree of node are less than node.item and all the integers in the right subtree of node are greater than or equal to node.item. Prove that the following recursive subroutine prints all the integers in a binary sort tree in non-decreasing order:
void SortPrint(BinaryTreeNode root) { // Assume that root is a pointer to the // root node of a binary sort tree. This // subroutine prints the integers in the // tree in non-decreasing order. if (root == null) { // There is nothing to print. } else { SortPrint(root.left); System.out.println(root.item); SortPrint(root.right); } }
Figure 3.1: Fibonacci numbers occur in nature, as in this model of the florets in the head of a sunflower.