Insert into a Binary Search Tree (BST) Editorial

Practice Problem Link: Insert into a Binary Search Tree (BST)

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given the root node of a binary search tree and a key, add the key in the tree and return the root node.

Note: The tree contains only unique values. Assume that the key does not already exist in the BST.

There can be multiple solutions. You can return the root node containing any of the solutions as long as the tree is a BST.

Approach

The idea is to insert the key at a leaf node. Traverse the given BST recursively and for each node:

• If the node is greater than the key then the key must be inserted in the left subtree. Recursively call the left subtree.
• If the node is smaller than the key then the key must be inserted in the right subtree. Recursively call the right subtree.

Repeat the above step until a leaf node is reached and insert the given key at that leaf node.

Analysis

• Time Complexity: O(Height of BST)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/

Node* insertBst(Node* root, int key) {
    if (root == NULL) {
		Node* newNode = new Node(key);
		root = newNode;
		return root;
	}
	if (key < root->data) {
		root->left = insertBst(root->left, key);
	} else {
		root->right = insertBst(root->right, key);
	}
	return root;
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/

	Node insertBst(Node root, int key) {
	    if (root == null) {
			Node newNode = new Node(key);
			root = newNode;
			return root;
		}
		if (key < root.data) {
			root.left = insertBst(root.left, key);
		} else {
			root.right = insertBst(root.right, key);
		}
		return root;
	}
}