BST_insertion

package prep_33_binarysearchtrees;

//Java program to demonstrate insert operation in binary search tree
public class BST_insertion {
	/* Class containing left and right child of current node and key value */
	public class Node {
		int key;
		Node left, right;

		public Node(int item) {
			key = item;
			left = right = null;
		}
	}

	// Root of BST
	Node root;

	// Constructor
	public BST_insertion() {
		root = null;
	}

	// This method mainly calls insertRec()
	public void insert(int key) {
		root = insertRec(root, key);
	}

	/* A recursive function to insert a new key in BST */
	public Node insertRec(Node root, int key) {
		if (root == null) { // If the tree is empty, return a new node
			root = new Node(key);
			return root;
		}
		if (key < root.key) // Otherwise, recur down the tree
			root.left = insertRec(root.left, key);
		else if (key > root.key)
			root.right = insertRec(root.right, key);
		return root; // return the (unchanged) node pointer
	}

	// This method mainly calls InorderRec()
	public void inorder() {
		inorderRec(root);
	}

	// A utility function to do inorder traversal of BST
	public void inorderRec(Node root) {
		if (root != null) {
			inorderRec(root.left);
			System.out.println(root.key);
			inorderRec(root.right);
		}
	}
}