Binary Search Tree Insertion Iterative Approach

This article concerns with writing the insert method for inserting a value in a binary search tree datastructure using iterative approach. Before continuing further you must have some basic knowledge about binary search tree data stucture.

Basically binary search tree is a hierarchical data structure in which each node has at most two child nodes (left node and righ node).  In binary search tree left and right nodes are arranged in such a way that for each node its left node contains key less than the node and right node contains the key greater than the node.

Now without going into much details about the binary tree lets start writing the code for a binary tree.

package ds.tree;

public class BStree {

	private Node root;

	public BStree(int rootData) {
		this.root = new Node(rootData);
	}

	static class Node {
		int data;
		Node left;
		Node right;

		public Node(int data) {
			this.data = data;
		}
	}

	public void insert(int data) {
		Node nNode = new Node(data);
		
		Node root = this.root;
		Node nodeB = null;
		while (root != null) {
			nodeB = root;
			if (root.data > data) {
				root = root.left;
			} else {
				root = root.right;
			}
		}
		if(data < nodeB.data)
			nodeB.left = nNode;
		else
			nodeB.right = nNode; 
	}
    
    // print to test code
    public void printTree() {
		System.out.print(root.data + ", " + root.left.data + ", " + root.right.data);
	}	
}

Notice that we have written a very simple print method to print only the root node key and its left and right node key. Lets write a simple test class to insert some elements in this binary tree and print it. We could have used some tree traversing strategy to print the keys but that is not necessary here because we are focused more on insertion strategy in a binary tree, so lets leave the tree traversal strategies for some other article.

package ds.tree;

public class BtreeMain {
	
	public static void main(String[] args) {
		BStree bst = new BStree(5);
		bst.insert(3);
		bst.insert(8);
		
		bst.printTree();
	}
}

Output :

5, 3, 8  

From above output we can be sure that values get inserted at the right place.