1. build123()

This is a very basic problem with a little pointer manipulation. (You can skip this problem if you are already comfortable with pointers.) Write code that builds the following little 1-2-3 binary search tree...

2
/ \
1 3

Write the code in three different ways...

a: by calling newNode() three times, and using three pointer variables

b: by calling newNode() three times, and using only one pointer variable

c: by calling insert() three times passing it the root pointer to build up the tree

(In Java, write a build123() method that operates on the receiver to change it to be the 1-2-3 tree with the given coding constraints. See Section 4.)

struct node* build123() {

2. size()

This problem demonstrates simple binary tree traversal. Given a binary tree, count the number of nodes in the tree.

int size(struct node* node) {

3. maxDepth()

Given a binary tree, compute its "maxDepth" -- the number of nodes along the longest path from the root node down to the farthest leaf node. The maxDepth of the empty tree is 0, the maxDepth of the tree on the first page is 3.

int maxDepth(struct node* node) {

4. minValue()

Given a non-empty binary search tree (an ordered binary tree), return the minimum data value found in that tree. Note that it is not necessary to search the entire tree. A maxValue() function is structurally very similar to this function. This can be solved with recursion or with a simple while loop.

int minValue(struct node* node) {

5. printTree()

Given a binary search tree (aka an "ordered binary tree"), iterate over the nodes to print them out in increasing order. So the tree...

4

/ \

2 5

/ \

1 3

Produces the output "1 2 3 4 5". This is known as an "inorder" traversal of the tree.

Hint: For each node, the strategy is: recur left, print the node data, recur right.

void printTree(struct node* node) {

6. printPostorder()

Given a binary tree, print out the nodes of the tree according to a bottom-up "postorder" traversal -- both subtrees of a node are printed out completely before the node itself is printed, and each left subtree is printed before the right subtree. So the tree...

4

/ \

2 5

/ \

1 3

Produces the output "1 3 2 5 4". The description is complex, but the code is simple. This is the sort of bottom-up traversal that would be used, for example, to evaluate an expression tree where a node is an operation like '+' and its subtrees are, recursively, the two subexpressions for the '+'.

void printPostorder(struct node* node) {

7. hasPathSum()

We'll define a "root-to-leaf path" to be a sequence of nodes in a tree starting with the root node and proceeding downward to a leaf (a node with no children). We'll say that an empty tree contains no root-to-leaf paths. So for example, the following tree has exactly four root-to-leaf paths:

5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1

Root-to-leaf paths:

path 1: 5 4 11 7

path 2: 5 4 11 2

path 3: 5 8 13

path 4: 5 8 4 1

For this problem, we will be concerned with the sum of the values of such a path -- for example, the sum of the values on the 5-4-11-7 path is 5 + 4 + 11 + 7 = 27.

Given a binary tree and a sum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Return false if no such path can be found. (Thanks to Owen Astrachan for suggesting this problem.)

int hasPathSum(struct node* node, int sum) {

8. printPaths()

Given a binary tree, print out all of its root-to-leaf paths as defined above. This problem is a little harder than it looks, since the "path so far" needs to be communicated between the recursive calls. Hint: In C, C++, and Java, probably the best solution is to create a recursive helper function printPathsRecur(node, int path[], int pathLen), where the path array communicates the sequence of nodes that led up to the current call. Alternately, the problem may be solved bottom-up, with each node returning its list of paths. This strategy works quite nicely in Lisp, since it can exploit the built in list and mapping primitives. (Thanks to Matthias Felleisen for suggesting this problem.)

Given a binary tree, print out all of its root-to-leaf paths, one per line.

void printPaths(struct node* node) {

9. mirror()

Change a tree so that the roles of the left and right pointers are swapped at every node.

So the tree...

4

/ \

2 5

/ \

1 3

is changed to...

4
/ \
5 2

/ \
3 1

The solution is short, but very recursive. As it happens, this can be accomplished without changing the root node pointer, so the return-the-new-root construct is not necessary. Alternately, if you do not want to change the tree nodes, you may construct and return a new mirror tree based on the original tree.

void mirror(struct node* node) {

10. doubleTree()

For each node in a binary search tree, create a new duplicate node, and insert the duplicate as the left child of the original node. The resulting tree should still be a binary search tree.

So the tree...

2
/ \
1 3

is changed to...

2
/ \
2 3

/	/
1	3
/
1

As with the previous problem, this can be accomplished without changing the root node pointer. void doubleTree(struct node* node) {

11. sameTree()

Given two binary trees, return true if they are structurally identical -- they are made of nodes with the same values arranged in the same way. (Thanks to Julie Zelenski for suggesting this problem.)

int sameTree(struct node* a, struct node* b) {

8. printPaths() Solution (C/C++)

/*
Given a binary tree, print out all of its root-to-leaf
paths, one per line. Uses a recursive helper to do the work.

*/
void printPaths(struct node* node) {
int path[1000];

printPathsRecur(node, path, 0);
}

/*
Recursive helper function -- given a node, and an array containing
the path from the root node up to but not including this node,
print out all the root-leaf paths.

*/
void printPathsRecur(struct node* node, int path[], int pathLen) {
if (node==NULL) return;

// append this node to the path array
path[pathLen] = node->data;
pathLen++;

// it's a leaf, so print the path that led to here
if (node->left==NULL && node->right==NULL) {

printArray(path, pathLen);
}
else {
// otherwise try both subtrees

printPathsRecur(node->left, path, pathLen);
printPathsRecur(node->right, path, pathLen);
}
}

// Utility that prints out an array on a line.

void printArray(int ints[], int len) {
int i;
for (i=0; i<len; i++) {

printf("%d ", ints[i]);
}
printf("\n");

}

9. mirror() Solution (C/C++)

/*
Change a tree so that the roles of the
left and right pointers are swapped at every node.

So the tree...

4
/ \
2 5

/ \
1 3

is changed to...

4
/ \
5 2

/ \

3 1
*/
void mirror(struct node* node) {

if (node==NULL) {

return;
}
else {

struct node* temp;

// do the subtrees
mirror(node->left);
mirror(node->right);

// swap the pointers in this node
temp = node->left;
node->left = node->right;
node->right = temp;

}
}

10. doubleTree() Solution (C/C++)

/*
For each node in a binary search tree,
create a new duplicate node, and insert
the duplicate as the left child of the original node.
The resulting tree should still be a binary search tree.

So the tree...
2
/ \

1 3

Is changed to...

2
/ \
2 3

/ /
1 3
/
1

*/
void doubleTree(struct node* node) {
struct node* oldLeft;

if (node==NULL) return;

// do the subtrees
doubleTree(node->left);
doubleTree(node->right);

// duplicate this node to its left
oldLeft = node->left;
node->left = newNode(node->data);
node->left->left = oldLeft;

}

11. sameTree() Solution (C/C++)

/*
Given two trees, return true if they are
structurally identical.

*/

int sameTree(struct node* a, struct node* b) {
// 1. both empty -> true
if (a==NULL && b==NULL) return(true);

// 2. both non-empty -> compare them
else if (a!=NULL && b!=NULL) {

return(
a->data == b->data &&
sameTree(a->left, b->left) &&
sameTree(a->right, b->right)

);
}
// 3. one empty, one not -> false
else return(false);

}

12. countTrees() Solution (C/C++)

/*
For the key values 1...numKeys, how many structurally unique

binary search trees are possible that store those keys.

Strategy: consider that each value could be the root.

Recursively find the size of the left and right subtrees.

*/

int countTrees(int numKeys) {

if (numKeys <=1) {

return(1);
}
else {

// there will be one value at the root, with whatever remains
// on the left and right each forming their own subtrees.
// Iterate through all the values that could be the root...
int sum = 0;
int left, right, root;

for (root=1; root<=numKeys; root++) {
left = countTrees(root - 1);
right = countTrees(numKeys - root);

// number of possible trees with this root == left*right
sum += left*right;
}

return(sum);
}
}

13. isBST1() Solution (C/C++)

/*
Returns true if a binary tree is a binary search tree.

*/

int isBST(struct node* node) {
if (node==NULL) return(true);

// false if the min of the left is > than us
if (node->left!=NULL && minValue(node->left) > node->data)
return(false);

// false if the max of the right is <= than us
if (node->right!=NULL && maxValue(node->right) <= node->data)
return(false);

// false if, recursively, the left or right is not a BST
if (!isBST(node->left) || !isBST(node->right))
return(false);

// passing all that, it's a BST
return(true);

}

14. isBST2() Solution (C/C++)

/*
Returns true if the given tree is a binary search tree
(efficient version).

*/
int isBST2(struct node* node) {
return(isBSTUtil(node, INT_MIN, INT_MAX));
}

/*
Returns true if the given tree is a BST and its
values are >= min and <= max.

*/
int isBSTUtil(struct node* node, int min, int max) {
if (node==NULL) return(true);

// false if this node violates the min/max constraint
if (node->data<min || node->data>max) return(false);

// otherwise check the subtrees recursively,
// tightening the min or max constraint
return

isBSTUtil(node->left, min, node->data) &&
isBSTUtil(node->right, node->data+1, max)
);
}

1. Build123() Solution (Java)

/**

Build 123 using three pointer variables.
*/
public void build123a() {

root = new Node(2);
Node lChild = new Node(1);
Node rChild = new Node(3);

root.left = lChild;
root.right= rChild;
}

/**

Build 123 using only one pointer variable.
*/
public void build123b() {

root = new Node(2);
root.left = new Node(1);
root.right = new Node(3);

}

/**
Build 123 by calling insert() three times.
Note that the '2' must be inserted first.

*/

public void build123c() {
root = null;
root = insert(root, 2);
root = insert(root, 1);
root = insert(root, 3);

}

2. size() Solution (Java)

/**
Returns the number of nodes in the tree.
Uses a recursive helper that recurs
down the tree and counts the nodes.

*/
public int size() {
return(size(root));
}

private int size(Node node) {
if (node == null) return(0);
else {

return(size(node.left) + 1 + size(node.right));
}
}

3. maxDepth() Solution (Java)

/**
Returns the max root-to-leaf depth of the tree.
Uses a recursive helper that recurs down to find
the max depth.

*/
public int maxDepth() {
return(maxDepth(root));
}

private int maxDepth(Node node) {
if (node==null) {

return(0);
}
else {

int lDepth = maxDepth(node.left);
int rDepth = maxDepth(node.right);

// use the larger + 1
return(Math.max(lDepth, rDepth) + 1);
}
}

4. minValue() Solution (Java)

/**
Returns the min value in a non-empty binary search tree.
Uses a helper method that iterates to the left to find
the min value.

*/
public int minValue() {
return( minValue(root) );
}

/**

Finds the min value in a non-empty binary search tree.
*/
private int minValue(Node node) {

Node current = node;
while (current.left != null) {
current = current.left;
}

return(current.data);
}

5. printTree() Solution (Java)

/**
Prints the node values in the "inorder" order.
Uses a recursive helper to do the traversal.

*/

public void printTree() {
printTree(root);
System.out.println();

}

private void printTree(Node node) {
if (node == null) return;

// left, node itself, right
printTree(node.left);
System.out.print(node.data + " ");
printTree(node.right);

}

6. printPostorder() Solution (Java)

/**
Prints the node values in the "postorder" order.
Uses a recursive helper to do the traversal.

*/

public void printPostorder() {
printPostorder(root);
System.out.println();

}

public void printPostorder(Node node) {
if (node == null) return;

// first recur on both subtrees
printPostorder(node.left);
printPostorder(node.right);

// then deal with the node
System.out.print(node.data + " ");
}

7. hasPathSum() Solution (Java)

/**
Given a tree and a sum, returns true if there is a path from the root
down to a leaf, such that adding up all the values along the path
equals the given sum.

Strategy: subtract the node value from the sum when recurring down,

and check to see if the sum is 0 when you run out of tree.
*/
public boolean hasPathSum(int sum) {

return( hasPathSum(root, sum) );
}

boolean hasPathSum(Node node, int sum) {
// return true if we run out of tree and sum==0
if (node == null) {

return(sum == 0);
}
else {
// otherwise check both subtrees

int subSum = sum - node.data;
return(hasPathSum(node.left, subSum) || hasPathSum(node.right, subSum));
}
}

8. printPaths() Solution (Java)

/**
Given a binary tree, prints out all of its root-to-leaf
paths, one per line. Uses a recursive helper to do the work.

*/

public void printPaths() {
int[] path = new int[1000];
printPaths(root, path, 0);

}

/**
Recursive printPaths helper -- given a node, and an array containing
the path from the root node up to but not including this node,
prints out all the root-leaf paths.

*/
private void printPaths(Node node, int[] path, int pathLen) {
if (node==null) return;

// append this node to the path array
path[pathLen] = node.data;
pathLen++;

// it's a leaf, so print the path that led to here
if (node.left==null && node.right==null) {

printArray(path, pathLen);
}
else {
// otherwise try both subtrees

printPaths(node.left, path, pathLen);
printPaths(node.right, path, pathLen);
}
}

/**

Utility that prints ints from an array on one line.
*/
private void printArray(int[] ints, int len) {

int i;
for (i=0; i<len; i++) {

System.out.print(ints[i] + " ");
}
System.out.println();

}

9. mirror() Solution (Java)

/**
Changes the tree into its mirror image.

So the tree...

4
/ \
2 5

/ \
1 3

is changed to...

4
/ \
5 2

/ \
3 1

Uses a recursive helper that recurs over the tree,

swapping the left/right pointers.

*/

public void mirror() {
mirror(root);

}

private void mirror(Node node) {
if (node != null) {
// do the sub-trees
mirror(node.left);
mirror(node.right);

// swap the left/right pointers
Node temp = node.left;
node.left = node.right;
node.right = temp;
}

}

10. doubleTree() Solution (Java)

/**
Changes the tree by inserting a duplicate node
on each nodes's .left.

So the tree...

2
/ \
1 3

Is changed to...
2

/ \
2 3

/	/
1	3
/
1

Uses a recursive helper to recur over the tree

and insert the duplicates.
*/
public void doubleTree() {

doubleTree(root);
}

private void doubleTree(Node node) {
Node oldLeft;

if (node == null) return;

// do the subtrees
doubleTree(node.left);
doubleTree(node.right);

// duplicate this node to its left
oldLeft = node.left;
node.left = new Node(node.data);
node.left.left = oldLeft;

}

11. sameTree() Solution (Java)

/*
Compares the receiver to another tree to
see if they are structurally identical.

*/
public boolean sameTree(BinaryTree other) {
return( sameTree(root, other.root) );
}

/**
Recursive helper -- recurs down two trees in parallel,
checking to see if they are identical.

*/

boolean sameTree(Node a, Node b) {
// 1. both empty -> true
if (a==null && b==null) return(true);

// 2. both non-empty -> compare them
else if (a!=null && b!=null) {

return(
a.data == b.data &&
sameTree(a.left, b.left) &&
sameTree(a.right, b.right)

);
}

// 3. one empty, one not -> false
else return(false);
}

12. countTrees() Solution (Java)

/**
For the key values 1...numKeys, how many structurally unique
binary search trees are possible that store those keys?

Strategy: consider that each value could be the root.

Recursively find the size of the left and right subtrees.
*/
public static int countTrees(int numKeys) {

if (numKeys <=1) {

return(1);
}
else {

// there will be one value at the root, with whatever remains
// on the left and right each forming their own subtrees.
// Iterate through all the values that could be the root...
int sum = 0;
int left, right, root;

for (root=1; root<=numKeys; root++) {
left = countTrees(root-1);
right = countTrees(numKeys - root);

// number of possible trees with this root == left*right
sum += left*right;
}

return(sum);
}
}

13. isBST1() Solution (Java)

/**
Tests if a tree meets the conditions to be a
binary search tree (BST).

*/
public boolean isBST() {
return(isBST(root));
}

/**
Recursive helper -- checks if a tree is a BST
using minValue() and maxValue() (not efficient).

*/
private boolean isBST(Node node) {
if (node==null) return(true);

// do the subtrees contain values that do not

// agree with the node?
if (node.left!=null && maxValue(node.left) > node.data) return(false);
if (node.right!=null && minValue(node.right) <= node.data) return(false);

// check that the subtrees themselves are ok
return( isBST(node.left) && isBST(node.right) );
}