Scientific Programming II

ModSim

Midterm Review

Helpful Hint

You may (and probably should) write private helper methods to implement solutions for these problems.

Problem 1

Write a method public void printPaths() which prints the path from the root to leaf for all the leaves in the binary search tree.

Example I/O

          78
     56
          23
2
     1
          0
               -1

1 - Insert a Value
2 - Print the Tree
3 - Root to Leaves
4 - Quit

3

Path from root to leaves:
2 1 0 -1
2 56 23 
2 56 78

Solution

public void printPaths()
{
   this.printPaths(this.root);
}

private void printPaths(Node node)
{
   if (node == null) return;
   else if (node.isLeaf()) {
       printPathsHelper(root, node.getData());
   } else {
       printPaths(node.getLeft());
       printPaths(node.getRight());
   }
}

private void printPathsHelper(Node node, int val)
{
   if (node.getData() == val) {
       System.out.println(node.getData());
   } else if (node.getData() > val) {
       System.out.print(node.getData() + " ");
       printPathsHelper(node.getLeft(), val);
   } else {
       System.out.print(node.getData() + " ");
       printPathsHelper(node.getRight(), val);
   }
}

Problem 2

Write a method public LinkedList<Integer> getPath(Node node) that returns a java.util.LinkedList<Integer> of the Nodes between the root and the argument Node.

Example I/O

          78
     56
          23
2
     1
          0
               -1

1 - Insert a Value
2 - Print the Tree
3 - Root to Leaves
4 - Get Path to Node
5 - Quit

4

Enter a node: 42

Node not found
Enter a node: 0

2 -> 1 -> 0

Note: The String representation of the LinkedList may differ from the example.

Helpful Hint

import java.util.LinkedList;

/** ... */

LinkedList<Integer> list = new LinkedList<>();

Solution

public LinkedList<Integer> getPath(Node node) 
{
   LinkedList<Integer> list = new LinkedList<>();
   
   if (!this.contains(node.getData())) {
       System.out.println("Node not found");
       return null;
   } else {
       return getPathHelper(this.root, node, list);
   }
}

private LinkedList<Integer> getPathHelper(Node curr,
                                         Node node, 
                                         LinkedList<Integer> list)
{
   if (curr == null) return list;
   
   list.add(curr.getData());
   
   if (curr.getData() == node.getData()) return list;
   else if (curr.getData() < node.getData()) {
       return getPathHelper(curr.getRight(), node, list);
   } else {
       return getPathHelper(curr.getLeft(), node, list);
   }
}

public boolean contains(int num)
{
   if (this.root.getData() == num) return true;
   else return containsHelper(num, this.root);
}

private boolean containsHelper(int num, Node node) 
{
   if (node == null) return false;
   
   if (num == node.getData()) return true;
   else if (num < node.getData()) {
       return containsHelper(num, node.getLeft());
   } else {
       return containsHelper(num, node.getRight());
   }
}

Problem 3

Write a method public void printBranches() which prints the values in the left branch and the right branch (of the root) of the binary search tree.

Example I/O

          78
     56
          23
2
     1
          0
               -1

1 - Insert a Value
2 - Print the Tree
3 - Root to Leaves
4 - Get Path to Node
5 - Print Branches
6 - Quit

5

Values of Left Branch of the Root
1, 0, -1 

Values of Right Branch of the Root
56, 23, 78

Solution

public void printBranches()
{
   System.out.println("Left subtree");
   printBranchesHelper(this.root.getLeft());
   System.out.println("\nRight subtree");
   printBranchesHelper(this.root.getRight());
   System.out.println();
}

private void printBranchesHelper(Node node)
{
   if (node != null) {
       System.out.print(node.getData() + " ");
       printBranchesHelper(node.getLeft());
       printBranchesHelper(node.getRight());
   }
}