Introduction to Binary Search Tree - The Coding Shala
Last Updated: 19-Jan-2021Home >> Data Structures >> Binary Search Tree
In this post, we will learn the basic Introduction of the Binary Search Tree.
Binary Search Tree
A binary search tree(BST), a special form of a binary tree that satisfies the following property:
- The value in each node must be greater than(or equal to) any values stored in its left subtree.
- The value in each node must be less than(or equal to) any values stored in its right subtree.
The following is an example of a binary search tree:
/ \ \
1 4 7
Like any other data structure, binary search trees(BSTs) support three main operations: search, insertion, and deletion.
Search in Binary Search Tree
To search a node in the Binary search tree we can
- Return the node if the target value is equal to the value of the node.
- Continue searching in the left subtree if the target value is less than the value of the node.
- Continue searching in the right subtree if the target value is larger than the value of the node.
Insertion in the Binary Search Tree
Another common operation in BST is to insert a new node. The main idea to insert a node is first we found out a proper leaf position for the target node and then insert the node as a leaf.
To insert a node we will:
Other Posts You May Like
- Search the left or right subtree according to the relation of the value of our target node.
- Repeat the above step until reaching an external node.
- Add the new node as its left or right child depending on the relation of the value of the node and the value of our target node.
Deletion in a Binary Search Tree
Deletion is more complicated than the insertion and searching in BST. There are three different cases while we delete a node.
- If the target node has no child then we can simply remove the node.
- If the target node has one child, we can use its child to replace itself.
- If the target node has two children, replace the node with its in-order successor or predecessor node and delete that node.
- Introduction to Binary Tree
- Binary Tree Preorder Traversal
- Binary Tree Inorder Traversal
- Binary Tree Postorder Traversal
- Binary Tree Level Order Traversal
Post a Comment