Insert a node into a BST
A new key is always inserted at the leaf. Start searching a key from the root till a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.
Code:
Below is the implementation of the Insertion of a single node in Binary Search Tree:
// Given Node Structure
struct node
{
int key;
struct node *left, *right;
};
// Function to create a new BST node
struct node* newNode(int item)
{
struct node* temp = (struct node*)malloc(
sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// Function to insert a new node with
// given key in BST
struct node* insert(struct node* node, int key)
{
// If the tree is empty, return a new node
if (node == NULL)
return newNode(key);
// Otherwise, recur down the tree
if (key < node->key)
{
node->left = insert(node->left, key);
}
else if (key > node->key)
{
node->right = insert(node->right, key);
}
// Return the node pointer
return node;
}
// Given Node Structure
struct node {
int key;
struct node *left, *right;
};
// Function to create a new BST node
struct node* newNode(int item)
{
struct node* temp
= (struct node*)malloc(
sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// Function to insert a new node with
// given key in BST
struct node* insert(struct node* node, int key)
{
// If the tree is empty, return a new node
if (node == NULL)
return newNode(key);
// Otherwise, recur down the tree
if (key < node->key) {
node->left = insert(node->left, key);
}
else if (key > node->key) {
node->right = insert(node->right, key);
}
// Return the node pointer
return node;
}
class GFG {
// Given Node Structure
static class node {
int key;
node left, right;
};
// Function to create a new BST node
static node newNode(int item)
{
node temp = new node();
temp.key = item;
temp.left = temp.right = null;
return temp;
}
// Function to insert a new node with
// given key in BST
static node insert(node node, int key)
{
// If the tree is empty, return a new node
if (node == null)
return newNode(key);
// Otherwise, recur down the tree
if (key < node.key) {
node.left = insert(node.left, key);
}
else if (key > node.key) {
node.right = insert(node.right, key);
}
// Return the node
return node;
}
}
# Given Node Structure
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
# Function to insert a new node with
# given key in BST
def insert(node, key):
# If the tree is empty, return a new node
if node is None:
return Node(key)
# Otherwise, recur down the tree
if key < node.key:
node.left = insert(node.left, key)
elif key > node.key:
node.right = insert(node.right, key)
# Return the node pointer
return node
// Given Node Structure
class Node
{
constructor(key){
this.key = key;
this.left = null;
this.right = null;
}
}
// Function to insert a new node with
// given key in BST
function insert(node, key)
{
// If the tree is empty, return a new node
if (node == null)
return new Node(key);
// Otherwise, recur down the tree
if (key < node.key)
{
node.left = insert(node.left, key);
}
else if (key > node.key)
{
node.right = insert(node.right, key);
}
// Return the node pointer
return node;
}
Time Complexity: O(N), where N is the number of nodes of the BST
Auxiliary Space: O(1)
Introduction to Binary Search Tree – Data Structure and Algorithm Tutorials
Binary Search Tree is a data structure used in computer science for organizing and storing data in a sorted manner. Binary search tree follows all properties of binary tree and its left child contains values less than the parent node and the right child contains values greater than the parent node. This hierarchical structure allows for efficient Searching, Insertion, and Deletion operations on the data stored in the tree.
Table of Content
- What is Binary Search Tree?
- Properties of Binary Search Tree
- Handling duplicate values in the Binary Search Tree
- Operations performed on a BST
- 1. Searching a node in BST
- 2. Insert a node into a BST
- 3. Delete a Node of BST
- 4. Traversal (Inorder traversal of BST)
- Applications of BST
- Advantages
- Disadvantages
- FAQ’s (Frequently asked questions) on Binary Search Tree: