Complexity of BST

Introduction

A Binary Search Tree, also known as an ordered Binary Tree, is a variant of a Binary Tree with a strict condition based on node value.

For all the nodes in a BST, the values of all the nodes in the left sub-tree of the current node are less than or equal to the value of the node itself. All the node values in the right subtree are greater than the value of the current node. This is referred to as the BST rule.

Rule for a Binary Search Tree

Let’s see how the above equation fits in a real example of a tree. Below, you can see a Binary Tree following a strict rule for ordering nodes:

For example, in the above tree Node Y is a parent node having two child nodes, SubTree 1 and SubTree 2 respectively. To convert a binary tree into a binary search tree, we need to follow a general rule. According to that rule, all nodes in SubTree 1 will have a value less than Node Y, and similarly, all nodes in SubTree 2 will have a value greater than Node Y.

Therefore, the value of Node Y will be less than X and the value of SubTree 3 is greater than Node X.

Insertion in Binary Search Trees

//recursive approach
class Node {

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

	public void insert(int value) {
		if (value <= data) {
			if (left == null) {
				left = new Node(value);
			} else {
					left.insert(value);
			}
		} else {
			if (right == null) {
				right = new Node(value);
			} else {
				right.insert(value);
			}
		}
	}
}

//iterative approach
class Node {

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

	public void insert(int value) {
		Node node = this;
		while (true) {
			if (node.data > value) {
				if (left == null) {
	        left = new Node(value);
					node.left = left;
          return true;
				}
        node = left;
			} else {
				if (right == null) {
	        right = new Node(value);
          node.right = right;
          return true;
				}
        node = right;
			}
		}
	}
}