Binary Search Tree Insertion Recursive Approach

In this article we will see how we can write the insert method for a binary tree using recursive approach. We have already covered the iterative approach in this article - Binary Search Tree Insertion Iterative Approach with some basic details about binary search tree data structure.

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 insertRecursive(int data) {
		insertRec(this.root, data);
	}
	
	private Node insertRec(Node root, int data) {
		if(root == null)
			return new Node(data);
		
		if(root.data < data)
			root.right = insertRec(root.right, data);
		else
			root.left = insertRec(root.left, data);
		return root;
	}

	public void printTree() {
		System.out.print(root.data + ", " + root.left.data + ", " + root.right.data);
	}
}

Notice that we have written a simple print method that will print the root node key with its two children nodes. Using this print method we can test out nsert method.
Now lets write a main class which will insert some values in this binary tree and print the keys using its print method.

package ds.tree;

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

Output :

5, 3, 8