Introduction
Figure 1 shows a Binary Search Tree. This post will start with the motivation of studying BST and gradually move to the related definitions. We will do some hands on coding for simple BST operations and we will end the post by analysing the drawbacks.
Where do we use Binary Search Tree?
- Trees show relationships in the data
- Trees have efficient insertion and searching
- Trees are flexible. It allows moving subtrees with minimum effort
- Binary Search Tree or BST is a data structure which can be used to store the data in a sorted manner
- BST can act as a priority queue, i.e. can help in retrieving maximum and minimum fast
Terminology
We will discuss some terminology related to Binary Search Tree here:
Node
A binary tree is made of nodes. Each node contains a reference to “left” and “right” element. It also has a data element . Root is the top most node of a tree.
For any node A, except for the root node, we define parent node B as the node which connects A with a direct edge.
Each node can be connected to arbitrary number of nodes, also called as children. Nodes without children are called leaves or external nodes. Nodes other than external nodes are called internal nodes.
Binary Tree
Any tree where all the nodes have at max two children is called Binary Tree. Figure 1 shows an example of Binary Tree.
Binary Search Tree
Binary Search Tree is a special case of Binary Tree where all the data element of nodes to the left of any parent node is less than the data element of the parent node. Also, the data element of nodes to the right of any parent node is greater than the data element of the parent node.
Figure 1 is an example of a BST.
Depth of a Node
Depth of a node is defined as number of edges from the root to the node. Node with data element 2 in figure 1 has depth of 1.
Height of Node
The height of a node is defined as the number of edges from the node to the deepest leaf. Node with data element 2 in figure 1 has height of 1. Height of tree is the height of the parent node.
Complete Binary Tree
A complete binary tree is a binary tree is defined as the tree in which each node has exactly zero or two children. Only possible exception can be bottom level, which is filled from left to right.
Figure 1 is an example of complete binary tree.
Quick test. Is the test shown in figure 4 a complete binary tree?
Codes For Insertion, Search and Transversal
Searching in a BST has O(tree height) worst-case runtime complexity. Binary search tree with n nodes has a minimum of O(log n) levels. It will take at least O(log n) comparisons to find a particular node. A binary search tree can be hugely unbalanced, making the search time to O(n).
Node class.
| /** | |
| * Node of the Binary Tree | |
| */ | |
| public class Node { | |
| private Integer data; | |
| private Node left; | |
| private Node right; | |
| public Integer getData() { | |
| return data; | |
| } | |
| public void setData(Integer data) { | |
| this.data = data; | |
| } | |
| public Node getLeft() { | |
| return left; | |
| } | |
| public void setLeft(Node left) { | |
| this.left = left; | |
| } | |
| public Node getRight() { | |
| return right; | |
| } | |
| public void setRight(Node right) { | |
| this.right = right; | |
| } | |
| public Node(Integer data, Node left, Node right) { | |
| this.data = data; | |
| this.left = left; | |
| this.right = right; | |
| } | |
| } |
| public class BinarySearchTree { | |
| public static void main(String args[]){ | |
| System.out.println("*******************Binary Search Tree******************"); | |
| Node tree = insert(5, null); | |
| insert(3, tree); | |
| insert(2, tree); | |
| insert(4, tree); | |
| insert(7, tree); | |
| insert(6, tree); | |
| insert(8, tree); | |
| System.out.println("*******************Inorder Binary Tree Transversal******************"); | |
| inorderTransversal(tree); | |
| System.out.println("*******************Preorder Binary Tree Transversal******************"); | |
| preorderTransversal(tree); | |
| System.out.println("*******************Postorder Binary Tree Transversal******************"); | |
| postorderTransversal(tree); | |
| System.out.println("*******************Searching in Binary Tree ******************"); | |
| searchBST(6, tree); | |
| searchBST(11, tree); | |
| } | |
| /** | |
| * @param node | |
| * @param key | |
| */ | |
| private static void searchBST(int key, Node node) { | |
| if(node == null) | |
| System.out.println("Key not found in the tree"); | |
| else if(node.getData().equals(key)) | |
| System.out.println("Key found in the tree"); | |
| else if(key > node.getData()) | |
| searchBST(key, node.getRight()); | |
| else if(key < node.getData()) | |
| searchBST(key, node.getLeft()); | |
| } | |
| public static Node insert(Integer key, Node node){ | |
| /** | |
| * Node is null. This means tree doesn't exist yet. | |
| * So, we will just initialize a node and return | |
| */ | |
| if(node == null) { | |
| return new Node(key, null, null); | |
| } | |
| if(key > node.getData()) | |
| node.setRight(insert(key, node.getRight())); | |
| if(key < node.getData()) | |
| node.setLeft(insert(key, node.getLeft())); | |
| return node; | |
| } | |
| /** | |
| * Inorder Transversal prints in a sorted order. | |
| * Prints root in between the left and right children | |
| * @param node | |
| */ | |
| public static void inorderTransversal(Node node) { | |
| if(node == null) | |
| return; | |
| inorderTransversal(node.getLeft()); | |
| System.out.println(node.getData()); | |
| inorderTransversal(node.getRight()); | |
| } | |
| /** | |
| * Prints root before the left and right node | |
| * @param node | |
| */ | |
| public static void preorderTransversal(Node node) { | |
| if(node == null) | |
| return; | |
| System.out.println(node.getData()); | |
| preorderTransversal(node.getLeft()); | |
| preorderTransversal(node.getRight()); | |
| } | |
| /** | |
| * Prints root after the left and right node | |
| * @param node | |
| */ | |
| public static void postorderTransversal(Node node) { | |
| if(node == null) | |
| return; | |
| postorderTransversal(node.getLeft()); | |
| postorderTransversal(node.getRight()); | |
| System.out.println(node.getData()); | |
| } | |
| } |
Disadvantage of Binary Search Tree
- The shape of the tree depends on the order of insertions. At worst case, tree can be hugely unbalanced. That means, we might have to travel all the way down the height of tree to find a key
- Key of each visited node has to be compared with the key of the element to be inserted/found while inserting or searching. If key are long then the run time may increase.
Reference:
https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html
https://en.wikipedia.org/wiki/Binary_search_tree#Examples_of_applications
If you liked this article and would like one such blog to land in your inbox every week, consider subscribing to our newsletter: https://skillcaptain.substack.com
Leave a Reply