The code for binary search tree written in class on Thursday., Oct. 21th. Includes the IntNode class, the IntBST class. Demonstrates a recursive in-order traversal.

public class IntNode {
    private IntNode left, right;
    private int data;
    
    public IntNode(int d){
	data = d;
    }
    
    public IntNode getLeft(){
	return left;
    }
    
    public IntNode getRight(){
	return right;
    }
    public void setLeft(IntNode in){
	left = in;
    }
    public void setRight(IntNode in){
	right = in;
    }
    
    public int getData() {
	return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public void inOrder() {
	if (left != null) left.inOrder();
	System.out.println(data);
	if (right != null) right.inOrder();    
    }
    
}


public class IntBST {
    private IntNode root;
    
    public IntBST() {
    }
    
    public boolean isEmpty() {
	return (root == null);
    }
    
    public IntNode getRoot(){
	return root;
    }
    
    // return the reference to the IntNode containing data
    // null if there is no such node
    // This is the search method written by Steve and, independently,
    // by Kyle and Eugene
    public IntNode search(int data ) {
        IntNode node = root;

        while (node != null && data != node.getData()){
            if (data > node.getData()){
                node = node.getRight();
            } else {
                node = node.getLeft();
            }
        }
        return node;
    }
    
    // insert the data into the binary serach tree
    // return the reference to the new node containing data
    // if there already is such a node, return null
    public IntNode insert(int data) {
        if(!isEmpty()){
            IntNode parent = getRoot();
            IntNode child;
            if (data == parent.getData()) {
                return null;
            }
            if(data < parent.getData()){
                child = parent.getLeft();
            } else {
                child = parent.getRight();
            }
       
            while(child != null){
                if(data < child.getData()){
                    parent = child;
                    child = child.getLeft();
                } 
                else if (data > child.getData()) {
                    parent = child;
                    child = child.getRight();
                }
                else return null;
            }
            IntNode node = new IntNode(data);
            if(parent.getData() < data){
                parent.setRight(node);
            }
            else{
                parent.setLeft(node);    
            }
            return node;
        }
	// if the tree is empty
        IntNode node = new IntNode(data);
        root = node;
        return node;
    }
	
    public void inOrder() {
        if (root != null) root.inOrder();
    }
}


This is an example from CSci 2101 course.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.