draw a binary search tree
What is Binary Search Tree?
A binary Search Tree is a node-based binary tree data structure which has the following properties:
- The left subtree of a node contains only nodes with keys lesser than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- The left and right subtree each must also be a binary search tree.
There must be no duplicate nodes.
The above properties of Binary Search Tree provides an ordering among keys so that the operations like search, minimum and maximum can be done fast. If there is no ordering, then we may have to compare every key to search for a given key.
How to search a key in given Binary Tree?
For searching a value, if we had a sorted array we could have performed a binary search. Let's say we want to search a number in the array, in binary search, we first define the complete list as our search space, the number can exist only within the search space. Now we compare the number to be searched or the element to be searched with the middle element (median) of the search space and if the record being searched is less than the middle element, we go searching in the left half, else we go searching in the right half, in case of equality we have found the element. In binary search, we start with 'n' elements in search space and if the mid element is not the element that we are looking for, we reduce the search space to 'n/2' we keep reducing the search space until we either find the record that we are looking for or we get to only one element in search space and be done with this whole reduction.
Search operations in binary search trees will be very similar. Let's say we want to search for the number, we start at the root, and then we compare the value to be searched with the value of the root, if it's equal we are done with the search if it's smaller we know that we need to go to the left subtree because in a binary search tree all the elements in the left subtree are smaller and all the elements in the right subtree are larger. Searching an element in the binary search tree is basically this traversal, at each step we go either left or right and at each step we discard one of the sub-trees. If the tree is balanced (we call a tree balanced if for all nodes the difference between the heights of left and right subtrees is not greater than one) we start with a search space of 'n' nodes and as we discard one of the sub-trees, we discard 'n/2' nodes so our search space gets reduced to 'n/2'. In the next step, we reduce the search space to 'n/4' and we repeat until we find the element or our search space is reduced to only one node. The search here is also a binary search hence the name; Binary Search Tree.
Implementation:
C++
struct
node* search(
struct
node* root,
int
key)
{
if
(root == NULL || root->key == key)
return
root;
if
(root->key < key)
return
search(root->right, key);
return
search(root->left, key);
}
Java
public
Node search(Node root,
int
key)
{
if
(root==
null
|| root.key==key)
return
root;
if
(root.key < key)
return
search(root.right, key);
return
search(root.left, key);
}
Python
def
search(root,key):
if
root
is
None
or
root.val
=
=
key:
return
root
if
root.val < key:
return
search(root.right,key)
return
search(root.left,key)
C#
public
Node search(Node root,
int
key)
{
if
(root ==
null
||
root.key == key)
return
root;
if
(root.key < key)
return
search(root.right, key);
return
search(root.left, key);
}
Javascript
<script>
function
search(root, key)
{
if
(root ==
null
||
root.key == key)
return
root;
if
(root.key < key)
return
search(root.right, key);
return
search(root.left, key);
}
</script>
Illustration to search 6 in below tree:
- Start from the root.
- Compare the searching element with root, if less than root, then recursively call left subtree, else recursively call right subtree.
- If the element to search is found anywhere, return true, else return false.
Insertion of a key :
A new key is always inserted at the leaf. We start searching for a key from the root until we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.
100 100
/ \ Insert 40 / \
20 500 ———> 20 500
/ \ / \
10 30 10 30
\
40
Implementation:
C++
#include <iostream>
using
namespace
std;
class
BST {
int
data;
BST *left, *right;
public
:
BST();
BST(
int
);
BST* Insert(BST*,
int
);
void
Inorder(BST*);
};
BST ::BST()
: data(0)
, left(NULL)
, right(NULL)
{
}
BST ::BST(
int
value)
{
data = value;
left = right = NULL;
}
BST* BST ::Insert(BST* root,
int
value)
{
if
(!root) {
return
new
BST(value);
}
if
(value > root->data) {
root->right = Insert(root->right, value);
}
else
if
(value < root->data){
root->left = Insert(root->left, value);
}
return
root;
}
void
BST ::Inorder(BST* root)
{
if
(!root) {
return
;
}
Inorder(root->left);
cout << root->data << endl;
Inorder(root->right);
}
int
main()
{
BST b, *root = NULL;
root = b.Insert(root, 50);
b.Insert(root, 30);
b.Insert(root, 20);
b.Insert(root, 40);
b.Insert(root, 70);
b.Insert(root, 60);
b.Insert(root, 80);
b.Inorder(root);
return
0;
}
C
#include <stdio.h>
#include <stdlib.h>
struct
node {
int
key;
struct
node *left, *right;
};
struct
node* newNode(
int
item)
{
struct
node* temp
= (
struct
node*)
malloc
(
sizeof
(
struct
node));
temp->key = item;
temp->left = temp->right = NULL;
return
temp;
}
void
inorder(
struct
node* root)
{
if
(root != NULL) {
inorder(root->left);
printf
(
"%d \n"
, root->key);
inorder(root->right);
}
}
struct
node* insert(
struct
node* node,
int
key)
{
if
(node == NULL)
return
newNode(key);
if
(key < node->key)
node->left = insert(node->left, key);
else
if
(key > node->key)
node->right = insert(node->right, key);
return
node;
}
int
main()
{
struct
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
class
BinarySearchTree {
class
Node {
int
key;
Node left, right;
public
Node(
int
item)
{
key = item;
left = right =
null
;
}
}
Node root;
BinarySearchTree() { root =
null
; }
BinarySearchTree(
int
value) { root =
new
Node(value); }
void
insert(
int
key) { root = insertRec(root, key); }
Node insertRec(Node root,
int
key)
{
if
(root ==
null
) {
root =
new
Node(key);
return
root;
}
else
if
(key < root.key)
root.left = insertRec(root.left, key);
else
if
(key > root.key)
root.right = insertRec(root.right, key);
return
root;
}
void
inorder() { inorderRec(root); }
void
inorderRec(Node root)
{
if
(root !=
null
) {
inorderRec(root.left);
System.out.println(root.key);
inorderRec(root.right);
}
}
public
static
void
main(String[] args)
{
BinarySearchTree tree =
new
BinarySearchTree();
tree.insert(
50
);
tree.insert(
30
);
tree.insert(
20
);
tree.insert(
40
);
tree.insert(
70
);
tree.insert(
60
);
tree.insert(
80
);
tree.inorder();
}
}
Python
class
Node:
def
__init__(
self
, key):
self
.left
=
None
self
.right
=
None
self
.val
=
key
def
insert(root, key):
if
root
is
None
:
return
Node(key)
else
:
if
root.val
=
=
key:
return
root
elif
root.val < key:
root.right
=
insert(root.right, key)
else
:
root.left
=
insert(root.left, key)
return
root
def
inorder(root):
if
root:
inorder(root.left)
print
(root.val)
inorder(root.right)
r
=
Node(
50
)
r
=
insert(r,
30
)
r
=
insert(r,
20
)
r
=
insert(r,
40
)
r
=
insert(r,
70
)
r
=
insert(r,
60
)
r
=
insert(r,
80
)
inorder(r)
C#
using
System;
class
BinarySearchTree {
public
class
Node {
public
int
key;
public
Node left, right;
public
Node(
int
item)
{
key = item;
left = right =
null
;
}
}
Node root;
BinarySearchTree() { root =
null
; }
BinarySearchTree(
int
value) { root =
new
Node(value); }
void
insert(
int
key) { root = insertRec(root, key); }
Node insertRec(Node root,
int
key)
{
if
(root ==
null
) {
root =
new
Node(key);
return
root;
}
if
(key < root.key)
root.left = insertRec(root.left, key);
else
if
(key > root.key)
root.right = insertRec(root.right, key);
return
root;
}
void
inorder() { inorderRec(root); }
void
inorderRec(Node root)
{
if
(root !=
null
) {
inorderRec(root.left);
Console.WriteLine(root.key);
inorderRec(root.right);
}
}
public
static
void
Main(String[] args)
{
BinarySearchTree tree =
new
BinarySearchTree();
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
tree.inorder();
}
}
Javascript
<script>
class Node {
constructor(item) {
this
.key = item;
this
.left =
this
.right =
null
;
}
}
var
root =
null
;
function
insert(key) {
root = insertRec(root, key);
}
function
insertRec(root , key) {
if
(root ==
null
) {
root =
new
Node(key);
return
root;
}
if
(key < root.key)
root.left = insertRec(root.left, key);
else
if
(key > root.key)
root.right = insertRec(root.right, key);
return
root;
}
function
inorder() {
inorderRec(root);
}
function
inorderRec(root)
{
if
(root !=
null
) {
inorderRec(root.left);
document.write(root.key+
"<br/>"
);
inorderRec(root.right);
}
}
insert(50);
insert(30);
insert(20);
insert(40);
insert(70);
insert(60);
insert(80);
inorder();
</script>
Output
20 30 40 50 60 70 80
Illustration to insert 2 in below tree:
- Start from the root.
- Compare the inserting element with root, if less than root, then recursively call left subtree, else recursively call right subtree.
- After reaching the end, just insert that node at left(if less than current) or else right.
Time Complexity: The worst-case time complexity of search and insert operations is O(h) where h is the height of the Binary Search Tree. In the worst case, we may have to travel from root to the deepest leaf node. The height of a skewed tree may become n and the time complexity of search and insert operation may become O(n).
Implementation: Insertion using loop.
C++
#include <bits/stdc++.h>
using
namespace
std;
class
Node {
public
:
int
val;
Node* left;
Node* right;
Node(
int
val)
: val(val)
, left(NULL)
, right(NULL)
{
}
};
void
insert(Node*& root,
int
key)
{
Node* node =
new
Node(key);
if
(!root) {
root = node;
return
;
}
Node* prev = NULL;
Node* temp = root;
while
(temp) {
if
(temp->val > key) {
prev = temp;
temp = temp->left;
}
else
if
(temp->val < key) {
prev = temp;
temp = temp->right;
}
}
if
(prev->val > key)
prev->left = node;
else
prev->right = node;
}
void
inorder(Node* root)
{
Node* temp = root;
stack<Node*> st;
while
(temp != NULL || !st.empty()) {
if
(temp != NULL) {
st.push(temp);
temp = temp->left;
}
else
{
temp = st.top();
st.pop();
cout << temp->val <<
" "
;
temp = temp->right;
}
}
}
int
main()
{
Node* root = NULL;
insert(root, 30);
insert(root, 50);
insert(root, 15);
insert(root, 20);
insert(root, 10);
insert(root, 40);
insert(root, 60);
inorder(root);
return
0;
}
Java
import
java.util.*;
import
java.io.*;
class
GFG {
public
static
void
main (String[] args) {
BST tree=
new
BST();
tree.insert(
30
);
tree.insert(
50
);
tree.insert(
15
);
tree.insert(
20
);
tree.insert(
10
);
tree.insert(
40
);
tree.insert(
60
);
tree.inorder();
}
}
class
Node{
Node left;
int
val;
Node right;
Node(
int
val){
this
.val=val;
}
}
class
BST{
Node root;
public
void
insert(
int
key){
Node node=
new
Node(key);
if
(root==
null
) {
root = node;
return
;
}
Node prev=
null
;
Node temp=root;
while
(temp!=
null
){
if
(temp.val>key){
prev=temp;
temp=temp.left;
}
else
if
(temp.val<key){
prev=temp;
temp=temp.right;
}
}
if
(prev.val>key)
prev.left=node;
else
prev.right=node;
}
public
void
inorder(){
Node temp=root;
Stack<Node> stack=
new
Stack<>();
while
(temp!=
null
||!stack.isEmpty()){
if
(temp!=
null
){
stack.add(temp);
temp=temp.left;
}
else
{
temp=stack.pop();
System.out.print(temp.val+
" "
);
temp=temp.right;
}
}
}
}
Python3
class
GFG :
@staticmethod
def
main( args) :
tree
=
BST()
tree.insert(
30
)
tree.insert(
50
)
tree.insert(
15
)
tree.insert(
20
)
tree.insert(
10
)
tree.insert(
40
)
tree.insert(
60
)
tree.inorder()
class
Node :
left
=
None
val
=
0
right
=
None
def
__init__(
self
, val) :
self
.val
=
val
class
BST :
root
=
None
def
insert(
self
, key) :
node
=
Node(key)
if
(
self
.root
=
=
None
) :
self
.root
=
node
return
prev
=
None
temp
=
self
.root
while
(temp !
=
None
) :
if
(temp.val > key) :
prev
=
temp
temp
=
temp.left
elif
(temp.val < key) :
prev
=
temp
temp
=
temp.right
if
(prev.val > key) :
prev.left
=
node
else
:
prev.right
=
node
def
inorder(
self
) :
temp
=
self
.root
stack
=
[]
while
(temp !
=
None
or
not
(
len
(stack)
=
=
0
)) :
if
(temp !
=
None
) :
stack.append(temp)
temp
=
temp.left
else
:
temp
=
stack.pop()
print
(
str
(temp.val)
+
" "
, end
=
"")
temp
=
temp.right
if
__name__
=
=
"__main__"
:
GFG.main([])
C#
using
System;
using
System.Collections.Generic;
public
class
GFG {
public
static
void
Main(String[] args) {
BST tree =
new
BST();
tree.insert(30);
tree.insert(50);
tree.insert(15);
tree.insert(20);
tree.insert(10);
tree.insert(40);
tree.insert(60);
tree.inorder();
}
}
public
class
Node {
public
Node left;
public
int
val;
public
Node right;
public
Node(
int
val) {
this
.val = val;
}
}
public
class
BST {
public
Node root;
public
void
insert(
int
key) {
Node node =
new
Node(key);
if
(root ==
null
) {
root = node;
return
;
}
Node prev =
null
;
Node temp = root;
while
(temp !=
null
) {
if
(temp.val > key) {
prev = temp;
temp = temp.left;
}
else
if
(temp.val < key) {
prev = temp;
temp = temp.right;
}
}
if
(prev.val > key)
prev.left = node;
else
prev.right = node;
}
public
void
inorder() {
Node temp = root;
Stack<Node> stack =
new
Stack<Node>();
while
(temp !=
null
|| stack.Count!=0) {
if
(temp !=
null
) {
stack.Push(temp);
temp = temp.left;
}
else
{
temp = stack.Pop();
Console.Write(temp.val +
" "
);
temp = temp.right;
}
}
}
}
Output
10 15 20 30 40 50 60
Some Interesting Facts:
- Inorder traversal of BST always produces sorted output.
- We can construct a BST with only Preorder or Postorder or Level Order traversal. Note that we can always get inorder traversal by sorting the only given traversal.
- Number of unique BSTs with n distinct keys is Catalan Number
Related Links:
- Binary Search Tree Delete Operation
- Quiz on Binary Search Tree
- Coding practice on BST
- All Articles on BST
Source: https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/
0 Response to "draw a binary search tree"
Post a Comment