Data Structures | Binary Search Tree

In this article we will talk about Binary Search Tree.

What is the binary search tree?

Node based data structure with following properties:

  • The left subtree of node contains values that are lesser than node’s value
  • The right subtree of node contains values that are bigger than nodes’ value
  • Left and right subtrees are also binary search trees.

Which operations we can peform on binary search trees?

  • Insert value
  • Get minimum value
  • Get maximum value
  • Search value
  • Get height of tree
  • Delete value

Are they contains duplicates?

No

What about asymptotic complexity of operations?

Depends on “balance” property. In balanced trees - logarithmic complexity, in unbalanced trees - linear complexity.

What about space complexity?

Linear complexity

What about insert operation?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class BinarySearchTree {
    public Node root;
    public void insert(int val) {
        if (root == null) {
            root = new Node(val);
            return;
        } 
        insertRecursively(root, val); 
    }
    private Node insertRecursively(Node node, int val) {
        if (node == null) {
            node = new Node(val);
            return node;   
        }
        if (val > node.val) node.right = insertRecursively(node.right, val);
        if (val < node.val) node.left = insertRecursively(node.left, val);
        return node;
    }
}

If tree is empty then define root with value val, otherwise insert recursively into tree, until we find suitable place.insertRecursively function search for suitable place, if there is some insert new node and return newely created node, otherwise search suitable place in children’s subtrees and return given current node.

What about get maximum, minimum value operation?

1
2
3
4
5
6
7
8
public int getMaximum() throws Exception {
    if (root == null) throw new NullPointerException();
    return getMaximumRecursively(root);
}
private int getMaximumRecursively(Node node) {
    if (node.right != null) return getMaximumRecursively(node.right);
    return node.val;
}

As we know each node’s right children is bigger than current node, so the most biggest node is rightmost.

The same logic for minumum operation: 

1
2
3
4
5
6
7
8
public int getMinimum() throws Exception {
    if (root == null) throw new NullPointerException();
    return getMinimumRecursively(root);
}
private int getMinimumRecursively(Node node) {
    if (node.left != null) return getMinimumRecursively(node.left);
    return node.val;
}

What about search operation? 

1
2
3
4
5
6
7
8
9
public boolean search(int val) {
    return searchRecursively(root, val);
}
public boolean searchRecursively(Node node, int val) {
    if (node == null) return false;
    if (val > node.val) return searchRecursively(node.right, val);
    if (val < node.val) return searchRecursively(node.left, val);
    return true;
}

What about height operation? 

1
2
3
4
5
6
7
public int getHeight() {
    return getHeightRecursively(root);
}
public int getHeightRecursively(Node node) {
    if (node == null) return 0;
    return 1 + Math.max(getHeightRecursively(node.left), getHeightRecursively(node.right));
}

What about delete operation?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void deleteValue(int val) {
    deleteRecursively(root, val);
}
private Node deleteRecursively(Node node, int val) {
    if (node == null) return node;
    if (val > node.val) {
        node.right = deleteRecursively(node.right, val);
    } else if (val < node.val) {
        node.left = deleteRecursively(node.left, val);
    } else {
        if (node.left == null) return node.left;
        if (node.right == null) return node.right;
        int minNodeOnRightSubtreeValue = getMinimumRecursively(node.right);
        node.val = minNodeOnRightSubtreeValue;
        node.right = deleteRecursively(node.right, minNodeOnRightSubtreeValue);
    }
    return node;
}

If node do not present in tree, so nothings happens.

If deleting node has one child then return that child(change refference of node’s parent child to node’s child)

If deleting node has two childrens then find the smallest value in right subtree, setup that value to current node’s value and recursively delete smallest node.