I am trying to follow Trees tutorial at: http://cslibrary.stanford.edu/110/BinaryTrees.html
Here is the code I have written so far:
package trees.bst;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
/**
*
* @author sachin
*/
public class BinarySearchTree {
Node root = null;
class Node {
Node left = null;
Node right = null;
int data = 0;
public Node(int data) {
this.left = null;
this.right = null;
this.data = data;
}
}
public void insert(int data) {
root = insert(data, root);
}
public boolean lookup(int data) {
return lookup(data, root);
}
public void buildTree(int numNodes) {
for (int i = 0; i < numNodes; i++) {
int num = (int) (Math.random() * 10);
System.out.println("Inserting number:" + num);
insert(num);
}
}
public int size() {
return size(root);
}
public int maxDepth() {
return maxDepth(root);
}
public int minValue() {
return minValue(root);
}
public int maxValue() {
return maxValue(root);
}
public void printTree() { //inorder traversal
System.out.println("inorder traversal:");
printTree(root);
System.out.println("\n--------------");
}
public void printPostorder() { //inorder traversal
System.out.println("printPostorder traversal:");
printPostorder(root);
System.out.println("\n--------------");
}
public int buildTreeFromOutputString(String op) {
root = null;
int i = 0;
StringTokenizer st = new StringTokenizer(op);
while (st.hasMoreTokens()) {
String stNum = st.nextToken();
int num = Integer.parseInt(stNum);
System.out.println("buildTreeFromOutputString: Inserting number:" + num);
insert(num);
i++;
}
return i;
}
public boolean hasPathSum(int pathsum) {
return hasPathSum(pathsum, root);
}
public void mirror() {
mirror(root);
}
public void doubleTree() {
doubleTree(root);
}
public boolean sameTree(BinarySearchTree bst) { //is this tree same as another given tree?
return sameTree(this.root, bst.getRoot());
}
public void printPaths() {
if (root == null) {
System.out.println("print path sum: tree is empty");
}
List pathSoFar = new ArrayList();
printPaths(root, pathSoFar);
}
///-------------------------------------------Public helper functions
public Node getRoot() {
return root;
}
//Exporting a non public Type through public API
///-------------------------------------------Helper Functions
private boolean isLeaf(Node node) {
if (node == null) {
return false;
}
if (node.left == null && node.right == null) {
return true;
}
return false;
}
///-----------------------------------------------------------
private boolean sameTree(Node n1, Node n2) {
if ((n1 == null && n2 == null)) {
return true;
} else {
if ((n1 == null || n2 == null)) {
return false;
} else {
if ((n1.data == n2.data)) {
return (sameTree(n1.left, n2.left) && sameTree(n1.right, n2.right));
}
}
}
return false;
}
private void doubleTree(Node node) {
//create a copy
//bypass the copy to continue looping
if (node == null) {
return;
}
Node copyNode = new Node(node.data);
Node temp = node.left;
node.left = copyNode;
copyNode.left = temp;
doubleTree(copyNode.left);
doubleTree(node.right);
}
private void mirror(Node node) {
if (node == null) {
return;
}
Node temp = node.left;
node.left = node.right;
node.right = temp;
mirror(node.left);
mirror(node.right);
}
private void printPaths(Node node, List pathSoFar) {
if (node == null) {
return;
}
pathSoFar.add(node.data);
if (isLeaf(node)) {
System.out.println("path in tree:" + pathSoFar);
pathSoFar.remove(pathSoFar.lastIndexOf(node.data)); //only the current node, a node.data may be duplicated
return;
} else {
printPaths(node.left, pathSoFar);
printPaths(node.right, pathSoFar);
}
}
private boolean hasPathSum(int pathsum, Node node) {
if (node == null) {
return false;
}
int val = pathsum - node.data;
boolean ret = false;
if (val == 0 && isLeaf(node)) {
ret = true;
} else if (val == 0 && !isLeaf(node)) {
ret = false;
} else if (val != 0 && isLeaf(node)) {
ret = false;
} else if (val != 0 && !isLeaf(node)) {
//recurse further
ret = hasPathSum(val, node.left) || hasPathSum(val, node.right);
}
return ret;
}
private void printPostorder(Node node) { //inorder traversal
if (node == null) {
return;
}
printPostorder(node.left);
printPostorder(node.right);
System.out.print(" " + node.data);
}
private void printTree(Node node) { //inorder traversal
if (node == null) {
return;
}
printTree(node.left);
System.out.print(" " + node.data);
printTree(node.right);
}
private int minValue(Node node) {
if (node == null) {
//error case: this is not supported
return -1;
}
if (node.left == null) {
return node.data;
} else {
return minValue(node.left);
}
}
private int maxValue(Node node) {
if (node == null) {
//error case: this is not supported
return -1;
}
if (node.right == null) {
return node.data;
} else {
return maxValue(node.right);
}
}
private int maxDepth(Node node) {
if (node == null || (node.left == null && node.right == null)) {
return 0;
}
int ldepth = 1 + maxDepth(node.left);
int rdepth = 1 + maxDepth(node.right);
if (ldepth > rdepth) {
return ldepth;
} else {
return rdepth;
}
}
private int size(Node node) {
if (node == null) {
return 0;
}
return 1 + size(node.left) + size(node.right);
}
private Node insert(int data, Node node) {
if (node == null) {
node = new Node(data);
} else if (data <= node.data) {
node.left = insert(data, node.left);
} else {
node.right = insert(data, node.right);
}
//control should never reach here;
return node;
}
private boolean lookup(int data, Node node) {
if (node == null) {
return false;
}
if (node.data == data) {
return true;
}
if (data < node.data) {
return lookup(data, node.left);
} else {
return lookup(data, node.right);
}
}
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
int treesize = 5;
bst.buildTree(treesize);
//treesize = bst.buildTreeFromOutputString("4 4 4 6 7");
treesize = bst.buildTreeFromOutputString("3 4 6 3 6");
//treesize = bst.buildTreeFromOutputString("10");
for (int i = 0; i < treesize; i++) {
System.out.println("Searching:" + i + " found:" + bst.lookup(i));
}
System.out.println("tree size:" + bst.size());
System.out.println("maxDepth :" + bst.maxDepth());
System.out.println("minvalue :" + bst.minValue());
System.out.println("maxvalue :" + bst.maxValue());
bst.printTree();
bst.printPostorder();
int pathSum = 10;
System.out.println("hasPathSum " + pathSum + ":" + bst.hasPathSum(pathSum));
pathSum = 6;
System.out.println("hasPathSum " + pathSum + ":" + bst.hasPathSum(pathSum));
pathSum = 19;
System.out.println("hasPathSum " + pathSum + ":" + bst.hasPathSum(pathSum));
bst.printPaths();
bst.printTree();
//bst.mirror();
System.out.println("Tree after mirror function:");
bst.printTree();
//bst.doubleTree();
System.out.println("Tree after double function:");
bst.printTree();
System.out.println("tree size:" + bst.size());
System.out.println("Same tree:" + bst.sameTree(bst));
BinarySearchTree bst2 = new BinarySearchTree();
bst2.buildTree(treesize);
treesize = bst2.buildTreeFromOutputString("3 4 6 3 6");
bst2.printTree();
System.out.println("Same tree:" + bst.sameTree(bst2));
System.out.println("---");
}
}
Now the problem is that netbeans shows Warning: Exporting a non public Type through public API for function getRoot().
I write this function to get root of tree to be used in sameTree() function, to help comparison of "this" with given tree.
Perhaps this is a OOP design issue... How should I restructure the above code that I do not get this warning and what is the concept I am missing here?
