java binary tree implementation

Binary tree is a data structure that keeps the data in order by having each data wrapped in a node, and each node contains two pointers, one point to the left and one point to the right. the left pointer points to a node that contains data with value less than the current node, the right pointer points to a node that contains data with value greater than the current node. The java class IntBinaryTree below implements the binary tree with each node containing an integer value. It is an unbalanced binary tree. Binary tree contains no duplicates.

import java.util.Random;
import java.util.concurrent.atomic.AtomicBoolean;

public class IntBinaryTree {
	// Node class for creating each node in the tree
	class Node {
		public Node left;
		public Node right;
		int value;
		public Node(int value) {
			this.value = value;
		}
	}
	
	// private fields
	private Node rootNode;
	private int size = 0;	// tree size, the number of nodes in the tree
	
	// Insert the node
	private void insertNode(Node node, int value) {
		if (value < node.value) {
			if (node.left != null) {
				insertNode(node.left, value);
			} else {
				node.left = new Node(value);
				this.size++;
			}
		} else if (value > node.value) {
			if (node.right != null) {
				insertNode(node.right, value);
			} else {
				node.right = new Node(value);
				this.size++;
			}
		}
	}
	
	// Search a node in the tree
	private void findNode(Node node, int n, AtomicBoolean found) {
		if (node != null) {
			findNode(node.left, n, found);
			if (node.value == n) {
				found.set(true);
			}
			findNode(node.right, n, found);
		}
	}
	
	// Print the tree from left to right
	private void printBT(Node node) {
		if (node != null) {
			printBT(node.left);
			System.out.println(node.value);
			printBT(node.right);
		}		
	}
	
	// Public insert method, gets the value and then call insertNode to insert the value
	// in the appropriate position
	public void insert(int value) {
		if (this.rootNode == null) {
			this.rootNode = new Node(value);
			this.size++;
		} else {
			insertNode(this.rootNode, value);	
		}
	}
	
	// Public find method to find a value in the tree
	public boolean find(int n) {
		AtomicBoolean found = new AtomicBoolean();
		findNode(this.rootNode, n, found);
		return found.get();
	}
	
	// Return the size of the binary tree
	public int getSize() {
		return this.size;
	}
	
	// Public print method to print the values in the binary tree from left to right
	public void print() {
		printBT(this.rootNode);
	}

	// Test code
	// Even though the test size here is 100, but the number to be inserted are from 1 to 10
	// Since binary tree contains no duplicates, thus, the result will  likely be 1 to 10
	public static void main(String[] args) {
		IntBinaryTree bt = new IntBinaryTree();
		Random rand = new Random();
		int testSize = 100, maxNum = 10;
		for(int i=0; i<testSize; i++) {
			bt.insert(rand.nextInt(maxNum)+1);
		}
		bt.print();
		System.out.println("Tree size: " + bt.getSize());
		System.out.println("Found 2: " + bt.find(2));
		System.out.println("Found 22: " + bt.find(22));
	}
}

Output:

1
2
3
4
5
6
7
8
9
10
Tree size: 10
Found 2: true
Found 22: false

Search within Codexpedia

Custom Search

Search the entire web

Custom Search