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.

 

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog at WordPress.com.

Up ↑

%d bloggers like this: