draw a binary search tree using the insertion method
How to insert a node in Binary Search Tree using Iteration
You are given a binary search tree (BST) and a value to insert into the tree. Print inorder traversal of the BST after the insertion.
Example:
Input:To the given BST insert 40
Output:
Explanation:The new node 40 is a leaf node. Start searching from the root till a leaf node is hit, i.e while searching if a new value is greater than current node move to right child else to left child.
Input:To the given BST insert 600
Output:
Explanation: The new node 600 is a leaf node. Start searching from the root till a leaf node is hit, i.e while searching if a new value is greater than current node move to right child else to left child.
Approach:
As we all know that a new key is always inserted at the leaf node. so we start searching a key from root till we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node with the given value, while searching if the value of current node is greater then the given value then move to the left , else move to right
Follow the steps mentioned below to implement the idea:
- Start from the root and run a loop until a null pointer is reached.
- Keep the previous pointer of the current node stored.
- If the current node is null then create and insert the new node there and make it as one of the children of the parent/previous node depending on its value.
- If the value of current node is less than the new value then move to the right child of current node else move to the left child.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
struct Node *left, *right;
};
Node* newNode( int data)
{
Node* temp = new Node;
temp->key = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
Node* insert(Node* root, int key)
{
Node* newnode = newNode(key);
Node* x = root;
Node* y = NULL;
while (x != NULL) {
y = x;
if (key < x->key)
x = x->left;
else
x = x->right;
}
if (y == NULL)
y = newnode;
else if (key < y->key)
y->left = newnode;
else
y->right = newnode;
return y;
}
void Inorder(Node* root)
{
if (root == NULL)
return ;
else {
Inorder(root->left);
cout << root->key << " " ;
Inorder(root->right);
}
}
int main()
{
Node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
Inorder(root);
return 0;
}
Java
import java.util.*;
class solution {
static class Node {
int key;
Node left, right;
};
static Node newNode( int data)
{
Node temp = new Node();
temp.key = data;
temp.left = null ;
temp.right = null ;
return temp;
}
static Node insert(Node root, int key)
{
Node newnode = newNode(key);
Node x = root;
Node y = null ;
while (x != null ) {
y = x;
if (key < x.key)
x = x.left;
else
x = x.right;
}
if (y == null )
y = newnode;
else if (key < y.key)
y.left = newnode;
else
y.right = newnode;
return y;
}
static void Inorder(Node root)
{
if (root == null )
return ;
else {
Inorder(root.left);
System.out.print(root.key + " " );
Inorder(root.right);
}
}
public static void main(String args[])
{
Node root = null ;
root = insert(root, 50 );
insert(root, 30 );
insert(root, 20 );
insert(root, 40 );
insert(root, 70 );
insert(root, 60 );
insert(root, 80 );
Inorder(root);
}
}
Python3
class newNode:
def __init__( self , data):
self .key = data
self .left = None
self .right = self .parent = None
def insert(root, key):
newnode = newNode(key)
x = root
y = None
while (x ! = None ):
y = x
if (key < x.key):
x = x.left
else :
x = x.right
if (y = = None ):
y = newnode
elif (key < y.key):
y.left = newnode
else :
y.right = newnode
return y
def Inorder(root):
if (root = = None ):
return
else :
Inorder(root.left)
print (root.key, end = " " )
Inorder(root.right)
if __name__ = = '__main__' :
root = None
root = insert(root, 50 )
insert(root, 30 )
insert(root, 20 )
insert(root, 40 )
insert(root, 70 )
insert(root, 60 )
insert(root, 80 )
Inorder(root)
C#
using System;
class GFG {
class Node {
public int key;
public Node left, right;
};
static Node newNode( int data)
{
Node temp = new Node();
temp.key = data;
temp.left = null ;
temp.right = null ;
return temp;
}
static Node insert(Node root, int key)
{
Node newnode = newNode(key);
Node x = root;
Node y = null ;
while (x != null ) {
y = x;
if (key < x.key)
x = x.left;
else
x = x.right;
}
if (y == null )
y = newnode;
else if (key < y.key)
y.left = newnode;
else
y.right = newnode;
return y;
}
static void Inorder(Node root)
{
if (root == null )
return ;
else {
Inorder(root.left);
Console.Write(root.key + " " );
Inorder(root.right);
}
}
public static void Main(String[] args)
{
Node root = null ;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
Inorder(root);
}
}
Javascript
<script>
class Node
{
constructor()
{
this .key = 0;
this .left = null ;
this .right = null ;
}
};
function newNode(data)
{
var temp = new Node();
temp.key = data;
temp.left = null ;
temp.right = null ;
return temp;
}
function insert(root, key)
{
var newnode = newNode(key);
var x = root;
var y = null ;
while (x != null )
{
y = x;
if (key < x.key)
x = x.left;
else
x = x.right;
}
if (y == null )
y = newnode;
else if (key < y.key)
y.left = newnode;
else
y.right = newnode;
return y;
}
function Inorder(root)
{
if (root == null )
return ;
else
{
Inorder(root.left);
document.write( root.key + " " );
Inorder(root.right);
}
}
var root = null ;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
Inorder(root);
</script>
Output
20 30 40 50 60 70 80
Time Complexity: O(H), where H is the height of the BST.
Auxiliary Space: O(1)
Source: https://www.geeksforgeeks.org/insert-a-node-in-binary-search-tree-iteratively/
0 Response to "draw a binary search tree using the insertion method"
Post a Comment