Sunday, September 13, 2009

Binary Tree and its popular methods

This is something convenient I think to do a brief revision on Binary Tree other than reading about it on Wikipedia. This implementation demonstrates the construction of binary tree with some elements and the typical methods related to it such as:
[1] Pre-Order Traversal
[2] In-Order Traversal
[3] Post-Order Traversal
[4] Getting the size of the binary tree
[5] Get the minimum value
[6] Get the maximum value
[7] Get root value
[8] Inserting new elements

My implementation does not include duplication of elements. You may copy the code and test it yourself.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class BinaryTree {

private static class TreeNode {
TreeNode left;
TreeNode right;
int nodeValue;
TreeNode(int data) {
left = null;
right = null;
nodeValue = data;
}
}

private TreeNode root;

public BinaryTree() {
root = null;
}

public void constructBinaryTreeHardCoded() {
root = null;

root = new TreeNode(6);
//root = insertData(root, 6);

root = insertData(root, 2);
root = insertData(root, 7);
root = insertData(root, 1);
root = insertData(root, 4);
root = insertData(root, 9);
root = insertData(root, 3);
root = insertData(root, 5);
root = insertData(root, 8);
}

public void testHarness(){
root = null;

Random rand = new Random();
int rootValue = rand.nextInt( 20 ) + 1;
root = new TreeNode(rootValue);
System.out.println("Random seeded root value: " + rootValue);
int numberOfNodes = rand.nextInt( 18 ) + 1;
System.out.println("Random number of children to be generated: " + numberOfNodes);
for (int i = 0; i < numberOfNodes; i++) {
int randValue = rand.nextInt( 30 ) + 1;
System.out.println("Inserting: " + randValue);
root = insertData(root, randValue);
}
}

public TreeNode insertData(TreeNode node, int data) {
if (node == null) {
node = new TreeNode(data);
} else {
if (data < node.nodeValue) {
if (node.left != null) {
node.left = insertData(node.left, data);
} else {
node.left = new TreeNode(data);
System.out.println("Inserted " + data + " to the left of " + node.nodeValue);
}
} else if (data > node.nodeValue) {
if (node.right != null) {
node.right = insertData(node.right, data);
} else {
node.right = new TreeNode(data);
System.out.println("Inserted " + data + " to the right of " + node.nodeValue);
}
} else {
System.out.println("Not inserting " + data + " because it already exists in the tree");
}
}
return(node);
}

public boolean isIdenticalTree(BinaryTree comparedTree) {
return (isIdenticalTree(root, comparedTree.root));
}

private boolean isIdenticalTree(TreeNode first, TreeNode second) {
if (first == null && second == null) {
return true;
} else if (first != null && second != null) {
return (
first.nodeValue == second.nodeValue &&
isIdenticalTree(first.left, second.left) &&
isIdenticalTree(first.right, second.right)
);
} else {
return false;
}
}

public int getSize() {
return(setSize(root));
}

private int setSize(TreeNode node) {
if (node == null) {
return 0;
} else {
return(setSize(node.left) + 1 + setSize(node.right));
}
}

public void printTreeTraversal() {
System.out.print("Inorder Traversal: ");
printInOrder(root);
System.out.print("\nPreorder Traversal: ");
printPreOrder(root);
System.out.print("\nPostorder Traversal: ");
printPostOrder(root);
System.out.println();
}


private void printInOrder(TreeNode node) {
if (node == null) {
return;
}
printInOrder(node.left);
visitTreeNode(node);
printInOrder(node.right);
}

private void printPreOrder(TreeNode node) {
if (node == null) {
return;
}
visitTreeNode(node);
printPreOrder(node.left);
printPreOrder(node.right);
}

private void printPostOrder(TreeNode node) {
if (node == null) {
return;
}
printPostOrder(node.left);
printPostOrder(node.right);
visitTreeNode(node);
}

private void visitTreeNode(TreeNode node){
System.out.print(node.nodeValue + " ");
}

public int getMinValue() {
return (getMinValue(root));
}

private int getMinValue(TreeNode node) {
while (node.left != null) {
node = node.left;
}
return (node.nodeValue);
}


public int getMaxValue() {
return (getMaxValue(root));
}

private int getMaxValue(TreeNode node) {
while (node.right != null) {
node = node.right;
}
return (node.nodeValue);
}

public int getMaxDepth() {
int depth = getMaxDepth(root);
return ((depth > 0) ? (depth - 1) : 0);
}

private int getMaxDepth(TreeNode node) {
if (node == null) {
return 0;
} else {
int leftDepth = getMaxDepth(node.left);
int rightDepth = getMaxDepth(node.right);
return (((leftDepth > rightDepth) ? leftDepth : rightDepth) + 1);
}
}

public boolean containsData(int data) {
return(containsData(root, data));
}

private boolean containsData(TreeNode node, int data) {
if (node == null) {
return false;
}
if (data == node.nodeValue) {
return true;
} else if (data < node.nodeValue) {
return(containsData(node.left, data));
} else {
return(containsData(node.right, data));
}
}

public int getRootValue(){
return root.nodeValue;
}

public boolean containsSumInPath(int total) {
return( containsSumInPath(root, total) );
}

private boolean containsSumInPath(TreeNode node, int total) {
if (node == null) {
return(total == 0);
} else {
int remainder = total - node.nodeValue;
if (containsSumInPath(node.left, remainder) || containsSumInPath(node.right, remainder)) {
addPaths( remainder, node.nodeValue, total);
}
return(containsSumInPath(node.left, remainder) || containsSumInPath(node.right, remainder));
}
}

private ArrayList path = new ArrayList();

private void addPaths(int remainder, int currentNodeValue, int total){
if (!path.contains(currentNodeValue)) {
path.add(currentNodeValue);
}
}

public ArrayList getSumOfPath(){
Collections.reverse(path);
return path;
}

public static void main(String[] args) {
BinaryTree bTree1 = new BinaryTree();
BinaryTree bTree2 = new BinaryTree();

bTree1.constructBinaryTreeHardCoded();
System.out.println("Size of the binary tree: " + bTree1.getSize());
System.out.println("Root value in the binary tree: " + bTree1.getRootValue());
System.out.println("Smallest value in the binary tree: " + bTree1.getMinValue());
System.out.println("Largest value in the binary tree: " + bTree1.getMaxValue());
System.out.println("Maximum depth of the binary tree: " + bTree1.getMaxDepth());
System.out.println("Contains node value 4: " + bTree1.containsData(4));
System.out.println("Path has sum of 30: " + bTree1.containsSumInPath(30) + " = " + bTree1.getSumOfPath());
bTree1.printTreeTraversal();

System.out.println();

bTree2.testHarness();
System.out.println("Size of the binary tree: " + bTree2.getSize());
System.out.println("Root value in the binary tree: " + bTree2.getRootValue());
System.out.println("Smallest value in the binary tree: " + bTree2.getMinValue());
System.out.println("Largest value in the binary tree: " + bTree2.getMaxValue());
System.out.println("Maximum depth of the binary tree: " + bTree2.getMaxDepth());
System.out.println("Contains node value 11: " + bTree2.containsData(11));

Random rand = new Random();
int find = rand.nextInt( 30 ) + 1;
System.out.println("Path has sum of "+ find +": " + bTree2.containsSumInPath(find) + " = " + bTree2.getSumOfPath());
bTree2.printTreeTraversal();

System.out.println("Are identical binary trees: " + bTree1.isIdenticalTree(bTree2));

System.out.println("\nChanged elements in binary tree");
bTree2.constructBinaryTreeHardCoded();
System.out.println("Are identical binary trees: " + bTree1.isIdenticalTree(bTree2));
}
}

0 comments:

Post a Comment