Insertion of a Node in Binary Search Tree

First, define a Binary Search Tree, represented in Java as follows:

public class BST&lt;Key extends Comparable<Key>, Value> {

    // Node in the tree is a private class, the implementation details are not needed by the outside
    private class Node {
        private Key key;
        private Value value;
        private Node left, right;

        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
            left = right = null;
        }
    }
    // Root node
    private Node root;
    // Number of nodes in the tree
    private int count;
    // Constructor, default to an empty Binary Search Tree
    public BST() {
        root = null;
        count = 0;
    }
    // Returns the number of nodes in the Binary Search Tree
    public int size() {
        return count;
    }
    // Returns whether the Binary Search Tree is empty
    public boolean isEmpty() {
        return count == 0;
    }
}

Node represents a node, and count represents the number of nodes.

The following steps illustrate the insertion of element 61 into the given Binary Search Tree:

1. The element to be inserted, 61, is greater than 42, so compare it with the right child node of 42.
2. 61 is greater than 59, so move 61 to the position corresponding to the right subtree of 59, which is currently empty, and insert it directly as the right child of 59.

The insertion operation is also a recursive process, handling three cases: equal, greater than, and less than.

Java Example Code

Source Code Download: Download

src/tutorialpro/binary/BinarySearchTreeInsert.java File Code:

package tutorialpro.binary;

/**
 * Insert a new element into the Binary Search Tree
 */

public class BinarySearchTreeInsert&lt;Key extends Comparable<Key>, Value> {

    // Node in the tree is a private class, the implementation details are not needed by the outside
    private class Node {
        private Key key;
        private Value value;
        private Node left, right;

        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
            left = right = null;
        }
    }

    private Node root;  // Root node
    private int count;  // Number of nodes in the tree

    // Constructor, default to an empty Binary Search Tree
    public BinarySearchTreeInsert() {
        root = null;
        count = 0;
    }

    // Returns the number of nodes in the Binary Search Tree
    public int size() {
        return count;
    }

    // Returns whether the Binary Search Tree is empty
    public boolean isEmpty() {
        return count == 0;
    }

    // Insert a new (key, value) pair into the Binary Search Tree
    public void insert(Key key, Value value) {
        root = insert(root, key, value);
    }

    // Core code --- start
    // Insert node (key, value) into the Binary Search Tree rooted at node, using a recursive algorithm

// Returns the root of the binary search tree after inserting a new node
private Node insert(Node node, Key key, Value value) {
    if (node == null) {
        count++;
        return new Node(key, value);
    }
    if (key.compareTo(node.key) == 0)
        node.value = value;
    else if (key.compareTo(node.key) < 0)
        node.left = insert(node.left, key, value);
    else // key > node.key
        node.right = insert(node.right, key, value);

    return node;
}
// Core code --- end