A complete tutorial on Binary Tree

Introduction

bst
Figure 1 : Binary Search Tree

 

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.

Untitled Diagram (3)
Figure 2 : Pictorial representation of a node. Referred here is the top most node with data element 4 as shown in figure 1

For any node A, except for the root node, we define parent node B as the node which connects A with a direct edge.

Untitled Diagram-Page-2 (1)
Figure 3: Node A is the parent of node B and C. A is the root too

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?
Untitled Diagram-Page-2 (3)
Figure 4

 

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;
}
}
view raw Node.java hosted with ❤ by GitHub

 

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
Untitled Diagram-Page-2 (4).png
Figure 5: Searching 5 in the given tree will mean transversing the whole tree height
  • 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:

Introduction to Algorithm 

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

Up ↑

%d bloggers like this: