![\"Binary](\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/08\/TV-Binary-search-tree-in-DS-normal-image07.jpg\")
<\/a><\/p>\nImplementation of Binary Search Tree in C:<\/strong><\/p>\n#include <stdio.h>\n#include <stdlib.h>\n\nstruct Node {\n int key;\n struct node *left_child, *right_child;\n};\n\nstruct Node *new_node(int value) {\n struct Node *temp = (struct Node *)malloc(sizeof(struct Node));\n temp->key = value;\n temp->left_child = temp->right_child = NULL;\n return temp;\n}\n\nvoid inorder_traversal(struct Node *Root) {\n if (Root != NULL) {\n inorder_traversal(Root->left_child);\n printf(\"%d -> \", Root->key);\n inorder_traversal(Root->right_child);\n }\n}\n\nstruct Node *insertion(struct Node *Node, int key) {\n if (Node == NULL) \n return new_node(key);\n if (key < Node->key)\n Node->left_child = insertion(Node->left_child, key);\n else\n Node->right_child = insertion(Node->right_child, key);\n return node;\n}\n\nstruct Node *min_value(struct Node *Node) {\n struct Node *current = Node;\n while (current && current->left_child != NULL)\n current = current->left_child;\n return current;\n}\n\nstruct Node *deletion(struct Node *Root, int key) {\n if (Root == NULL) \n return Root;\n if (key < Root->key)\n Root->left_child = deletion(Root->left_child, key);\n else if (key > Root->key)\n Root->right_child = deletion(Root->right_child, key);\n else {\n if (Root->left_child == NULL) {\n struct Node *temp = Root->right_child;\n free(Root);\n return temp;\n } \n else if (Root->right_child == NULL) {\n struct Node *temp = Root->left_child;\n free(Root);\n return temp;\n }\n struct Node *temp = min_value(Root->right_child);\n Root->key = temp->key;\n Root->right_child = deletion(Root->right_child, temp->key);\n }\n return Root;\n}\n\nint main() {\n struct Node *root = NULL;\n root = insert(root, 200);\n root = insert(root, 100);\n root = insert(root, 40);\n root = insert(root, 120);\n root = insert(root, 130);\n root = insert(root, 300);\n root = insert(root, 250);\n root = insert(root, 360);\n root = insert(root, 110);\n printf(\"Inorder traversal: \");\n inorder_traversal(root);\n printf(\"\\nAfter deleting 10\\n\");\n root = deletion(root, 100);\n printf(\"Inorder traversal: \");\n inorder_traversal(root);\n}\n<\/pre>\nBinary Search Tree Implementation in C++:<\/h3>\n#include <stdio.h>\n#include <stdlib.h>\n\nstruct Node {\n int key;\n struct node *left_child, *right_child;\n};\n\nstruct Node *new_node(int value) {\n struct Node *temp = (struct Node *)malloc(sizeof(struct Node));\n temp->key = value;\n temp->left_child = temp->right_child = NULL;\n return temp;\n}\n\nvoid inorder_traversal(struct Node *Root) {\n if (Root != NULL) {\n inorder_traversal(Root->left_child);\n printf(\"%d -> \", Root->key);\n inorder_traversal(Root->right_child);\n }\n}\n\nstruct Node *insertion(struct Node *Node, int key) {\n if (Node == NULL) \n return new_node(key);\n if (key < Node->key)\n Node->left_child = insertion(Node->left_child, key);\n else\n Node->right_child = insertion(Node->right_child, key);\n return node;\n}\n\nstruct Node *min_value(struct Node *Node) {\n struct Node *current = Node;\n while (current && current->left_child != NULL)\n current = current->left_child;\n return current;\n}\n\nstruct Node *deletion(struct Node *Root, int key) {\n if (Root == NULL) \n return Root;\n if (key < Root->key)\n Root->left_child = deletion(Root->left_child, key);\n else if (key > Root->key)\n Root->right_child = deletion(Root->right_child, key);\n else {\n if (Root->left_child == NULL) {\n struct Node *temp = Root->right_child;\n free(Root);\n return temp;\n } \n else if (Root->right_child == NULL) {\n struct Node *temp = Root->left_child;\n free(Root);\n return temp;\n }\n struct Node *temp = min_value(Root->right_child);\n Root->key = temp->key;\n Root->right_child = deletion(Root->right_child, temp->key);\n }\n return Root;\n}\n\nint main() {\n struct Node *root = NULL;\n root = insertion(root, 200);\n root = insertion(root, 100);\n root = insertion(root, 40);\n root = insertion(root, 120);\n root = insertion(root, 130);\n root = insertion(root, 300);\n root = insertion(root, 250);\n root = insertion(root, 360);\n root = insertion(root, 110);\n printf(\"Inorder traversal: \");\n inorder_traversal(root);\n printf(\"\\nAfter deleting 10\\n\");\n root = deletion(root, 100);\n printf(\"Inorder traversal: \");\n inorder_traversal(root);\n}\n<\/pre>\nImplementation of Binary Search Tree in Java:<\/h3>\nclass BinarySearchTree {\n class Node {\n int key;\n Node left_child, right_child;\n\n public Node(int value) {\n key = value;\n left_child = right_child = null;\n }\n }\n\n Node root;\n\n BinarySearchTree() {\n root = null;\n }\n\n void insertion(int key) {\n root = insert_key(root, key);\n }\n\n Node insert_key(Node root, int key) {\n if (root == null) {\n root = new Node(key);\n return root;\n }\n if (key < root.key)\n root.left_child = insert_key(root.left_child, key);\n else if (key > root.key)\n root.right_child = insert_key(root.right_child, key);\n return root;\n }\n\n void inorder_traversal() {\n inorder_rec(root);\n }\n\n void inorder_rec(Node root) {\n if (root != null) {\n inorder_rec(root.left_child);\n System.out.print(root.key + \" -> \");\n inorder_rec(root.right_child);\n }\n }\n\n void deletion(int key) {\n root = deletion(root, key);\n }\n\n Node delete_rec(Node root, int key) {\n if (root == null)\n return root;\n if (key < root.key)\n root.left_child = delete_rec(root.left_child, key);\n else if (key > root.key)\n root.right_child = deletion(root.right_child, key);\n else {\n if (root.left_child == null)\n return root.right_child;\n else if (root.right_child == null)\n return root.left_child;\n root.key = min_value(root.right_child);\n root.right_child = delete_rec(root.right_child, root.key);\n }\n return root;\n }\n\n int min_value(Node root) {\n int minv = root.key;\n while (root.left_child != null) {\n minv = root.left_child.key;\n root = root.left_child;\n }\n return minv;\n }\n\n public static void main(String[] args) {\n BinarySearchTree tree = new BinarySearchTree();\n\n tree.insertion(200);\n tree.insertion(100);\n tree.insertion(40);\n tree.insertion(120);\n tree.insertion(130);\n tree.insertion(300);\n tree.insertion(250);\n tree.insertion(360);\n tree.insertion(110);\n\n System.out.print(\"Inorder traversal: \");\n tree.inorder_traversal();\n\n System.out.println(\"\\n\\nAfter deleting 10\");\n tree.deletion(100);\n System.out.print(\"Inorder traversal: \");\n tree.inorder_traversal();\n }\n}\n<\/pre>\nImplementation of BST in Python:<\/h3>\nclass Node:\n def __init__(self, key):\n self.key = key\n self.left_child = None\n self.right_child = None\n\ndef inorder_traversal(root):\n if root is not None:\n inorder_traversal(root.left_child)\n print(str(root.key) + \"->\", end=' ')\n inorder_traversal(root.right_child)\n\ndef insertion(Node, key):\n if Node is None:\n return Node(key)\n if key < Node.key:\n Node.left_child = insertion(node.left_child, key)\n else:\n node.right_child = insertion(node.right_child, key)\n return Node\n\ndef min_value(node):\n current = node\n while(current.left_child is not None):\n current = current.left_child\n return current\n\ndef deletion(root, key):\n if root is None:\n return root\n if key < root.key:\n root.left_child = deletion(root.left_child, key)\n elif(key > root.key):\n root.right_child = deletion(root.right_child, key)\n else:\n if root.left_child is None:\n temp = root.right_child\n root = None\n return temp\n elif root.right_child is None:\n temp = root.left_child\n root = None\n return temp\n temp = min_value(root.right_child)\n root.key = temp.key\n root.right_child = deletion(root.right_child, temp.key)\n return root\n\n\nroot = None\nroot = insertion(root, 200)\nroot = insertion(root, 100)\nroot = insertion(root, 40)\nroot = insertion(root, 120)\nroot = insertion(root, 130)\nroot = insertion(root, 300)\nroot = insertion(root, 250)\nroot = insertion(root, 360)\nroot = insertion(root, 110)\nprint(\"Inorder traversal: \", end=' ')\ninorder_traversal(root)\nprint(\"\\nDelete 100\")\nroot = deletion(root, 10)\nprint(\"Inorder traversal: \", end=' ')\ninorder_traversal(root)\n<\/pre>\nComplexity Analysis of Binary Search Tree:<\/h3>\n
Consider a tree having n nodes. Then, the time complexity of Binary Search Tree will be:<\/p>\n
\n\n\nScenario\/Operation\u00a0<\/strong><\/td>\nSearch\u00a0<\/strong><\/td>\nInsert\u00a0<\/strong><\/td>\nDelete\u00a0<\/strong><\/td>\n<\/tr>\n\n| Worst case<\/span><\/td>\n | O(n)<\/span><\/td>\n | O(n)<\/span><\/td>\n | O(n)<\/span><\/td>\n<\/tr>\n\n| Average case<\/span><\/td>\n | O(log n)<\/span><\/td>\n | O(log n)<\/span><\/td>\n | O(log n)<\/span><\/td>\n<\/tr>\n\n| Best case<\/span><\/td>\n | O(log n)<\/span><\/td>\n | O(log n)<\/span><\/td>\n | O(log n)<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n The space complexity in all operations is O(n).<\/p>\n Advantages of Binary Search Tree:<\/h3>\n\n- Searching is more efficient as compared to a simple binary tree.<\/li>\n
- The insertion and deletion operations are faster in a binary search tree in comparison to arrays and linked lists.<\/li>\n
- At each step, the binary search tree removes half the subtree and this makes it work faster.<\/li>\n<\/ul>\n
Applications of Binary Search Tree:<\/h3>\n\n- It is used in multi-level indexing in the database management system.<\/li>\n
- Used in UNIX kernel to manage virtual memory areas<\/li>\n
- Used in dynamic sorting of elements.<\/li>\n<\/ul>\n
Conclusion<\/h3>\nIn this article, we have seen the working of various operations such as insertion, deletion and searching in a binary search tree. We have also gone through the complexity analysis and various applications of a BST.<\/p>\n","protected":false},"excerpt":{"rendered":" A binary search tree(BST) is a special type of binary tree and is also known as a sorted or ordered binary tree. In a binary search tree: The value of the left node is...<\/p>\n","protected":false},"author":1,"featured_media":84104,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3555],"tags":[1985,4068,4069,4070],"class_list":["post-83520","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structure","tag-binary-search-tree","tag-binary-search-tree-in-data-structure","tag-deletion-in-binary-search-tree","tag-insertion-in-bst"],"yoast_head":"\n Binary Search Tree in Data Structure - TechVidvan<\/title>\n<meta name=\"description\" content=\"Learn about Binary Search tree in Data Structure. See various operations like insertion, deletion & searching in binary search tree.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/techvidvan.com\/tutorials\/binary-search-tree\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Binary Search Tree in Data Structure - TechVidvan\" \/>\n<meta property=\"og:description\" content=\"Learn about Binary Search tree in Data Structure. See various operations like insertion, deletion & searching in binary search tree.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/techvidvan.com\/tutorials\/binary-search-tree\/\" \/>\n<meta property=\"og:site_name\" content=\"TechVidvan\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/TechVidvan\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-08-18T03:30:53+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Binary-search-tree-in-DS.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1200\" \/>\n\t<meta property=\"og:image:height\" content=\"628\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"TechVidvan Team\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@vidvantech\" \/>\n<meta name=\"twitter:site\" content=\"@vidvantech\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"TechVidvan Team\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"12 minutes\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Binary Search Tree in Data Structure - TechVidvan","description":"Learn about Binary Search tree in Data Structure. See various operations like insertion, deletion & searching in binary search tree.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/techvidvan.com\/tutorials\/binary-search-tree\/","og_locale":"en_US","og_type":"article","og_title":"Binary Search Tree in Data Structure - TechVidvan","og_description":"Learn about Binary Search tree in Data Structure. See various operations like insertion, deletion & searching in binary search tree.","og_url":"https:\/\/techvidvan.com\/tutorials\/binary-search-tree\/","og_site_name":"TechVidvan","article_publisher":"https:\/\/www.facebook.com\/TechVidvan\/","article_published_time":"2021-08-18T03:30:53+00:00","og_image":[{"width":1200,"height":628,"url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Binary-search-tree-in-DS.jpg","type":"image\/jpeg"}],"author":"TechVidvan Team","twitter_card":"summary_large_image","twitter_creator":"@vidvantech","twitter_site":"@vidvantech","twitter_misc":{"Written by":"TechVidvan Team","Est. reading time":"12 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/techvidvan.com\/tutorials\/binary-search-tree\/#article","isPartOf":{"@id":"https:\/\/techvidvan.com\/tutorials\/binary-search-tree\/"},"author":{"name":"TechVidvan Team","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/person\/e9c26e74dd3d87421f7ada9433b8cd22"},"headline":"Binary Search Tree in Data Structure","datePublished":"2021-08-18T03:30:53+00:00","mainEntityOfPage":{"@id":"https:\/\/techvidvan.com\/tutorials\/binary-search-tree\/"},"wordCount":1227,"commentCount":0,"publisher":{"@id":"https:\/\/techvidvan.com\/tutorials\/#organization"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/binary-search-tree\/#primaryimage"},"thumbnailUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Binary-search-tree-in-DS.jpg","keywords":["Binary Search Tree","Binary Search Tree in Data Structure","Deletion in Binary search tree","Insertion in BST"],"articleSection":["Data Structure Tutorials"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/techvidvan.com\/tutorials\/binary-search-tree\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/techvidvan.com\/tutorials\/binary-search-tree\/","url":"https:\/\/techvidvan.com\/tutorials\/binary-search-tree\/","name":"Binary Search Tree in Data Structure - TechVidvan","isPartOf":{"@id":"https:\/\/techvidvan.com\/tutorials\/#website"},"primaryImageOfPage":{"@id":"https:\/\/techvidvan.com\/tutorials\/binary-search-tree\/#primaryimage"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/binary-search-tree\/#primaryimage"},"thumbnailUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Binary-search-tree-in-DS.jpg","datePublished":"2021-08-18T03:30:53+00:00","description":"Learn about Binary Search tree in Data Structure. See various operations like insertion, deletion & searching in binary search tree.","breadcrumb":{"@id":"https:\/\/techvidvan.com\/tutorials\/binary-search-tree\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/techvidvan.com\/tutorials\/binary-search-tree\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/techvidvan.com\/tutorials\/binary-search-tree\/#primaryimage","url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Binary-search-tree-in-DS.jpg","contentUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Binary-search-tree-in-DS.jpg","width":1200,"height":628,"caption":"Binary search tree in DS"},{"@type":"BreadcrumbList","@id":"https:\/\/techvidvan.com\/tutorials\/binary-search-tree\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/techvidvan.com\/tutorials\/"},{"@type":"ListItem","position":2,"name":"Binary Search Tree in Data Structure"}]},{"@type":"WebSite","@id":"https:\/\/techvidvan.com\/tutorials\/#website","url":"https:\/\/techvidvan.com\/tutorials\/","name":"TechVidvan Blogs","description":"","publisher":{"@id":"https:\/\/techvidvan.com\/tutorials\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/techvidvan.com\/tutorials\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/techvidvan.com\/tutorials\/#organization","name":"TechVidvan","url":"https:\/\/techvidvan.com\/tutorials\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/logo\/image\/","url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2024\/03\/techvidvan-logo-200x50-1.webp","contentUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2024\/03\/techvidvan-logo-200x50-1.webp","width":200,"height":50,"caption":"TechVidvan"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/TechVidvan\/","https:\/\/x.com\/vidvantech"]},{"@type":"Person","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/person\/e9c26e74dd3d87421f7ada9433b8cd22","name":"TechVidvan Team","description":"The TechVidvan Team delivers practical, beginner-friendly tutorials on programming, Java, Python, C++, DSA, AI, ML, data Science, Android, Flutter, MERN, Web Development, and technology. Our experts are here to help you upskill and excel in today\u2019s tech industry."}]}},"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts\/83520","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/comments?post=83520"}],"version-history":[{"count":0,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts\/83520\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/media\/84104"}],"wp:attachment":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/media?parent=83520"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/categories?post=83520"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/tags?post=83520"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}} | | | | | | |
![\"Binary](\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/08\/TV-Binary-search-tree-in-DS-normal-image01.jpg\")
<\/a><\/p>\n