Home » Data Structure & Algorithms » Binary Search Tree

Binary Search Tree

 

Binary Search tree or  BST or sorted binary tree is a binary tree in which each internal node X stores an element such that the element stored in the left subtree of X are less than or equal to X and elements stored in the right subtree of X are greater than or equal to X. The left and right subtree each must also be a binary search tree.Inorder traversal of binary tree always gives an ascending sorted array of elements.

 

Operations Average Case Complexity Worst Case Complexity
insertion O(log n) O(n)
search O(log n) O(n)
deletion O(log n) O(n)

BST creation takes O(n) space complexity.

Java Code for Binary Search Tree :

Problems :

1 : insert,search,delete and traversal operation in BST
2 : check if the given Binary tree is BST or not.
3 : Minimum value node in a binary search Tree

4 : Lowest Common Ancestor in a BST
 
 


Leave a comment

Your email address will not be published. Required fields are marked *

13 + 5 =