Binary Tree Data Structure
Welcome!! In this article, we will be learning about binary trees.
There are majorly two kinds of data structures. One is Linear Data structure and the other one is Non-Linear data structure. The data structure in which all the data elements are sequentially or linearly stored is called Linear data structure. The computer memory for all these elements will be arranged sequentially which means that elements are connected to previous and next nodes. In the linear data structure, a single level is involved. Therefore, we can traverse all the elements in a single run only. Eg., Arrays, Stacks, Queues, etc. Whereas in Non-Linear data structure, the data elements are not in sequential or linear order. A single level is not involved and hence single run is not possible. Tree Data structure comes under a Non-Linear data structure where data elements are not stored sequentially.
Tree Vocabulary:
- Root — The topmost element in the tree.
- Children — The elements that are directly under an element are called its children.
- Parent — The element directly above something is called its parent. Eg., b is the parent of d and e and a child of a.
- Leaves — The elements with no children are called leaf nodes.
- Edge — An edge connects two nodes.
Why Trees?
- One of the reasons to use trees is to store data that naturally forms a Tree structure. Eg., file system.
2. Trees (with some ordering e.g., BST) provide moderate access/search (quicker than Linked List and slower than arrays).
3. Trees provide moderate insertion/deletion (quicker than Arrays and slower than Unordered Linked Lists).
Let us see what a binary tree is. The Binary tree means that the node can have a maximum of two children. Here, the binary name itself suggests that ‘two’; therefore, each node can have either 0, 1, or 2 children.
Now, let us see how to implement a binary tree. A tree contains mainly 3 parts. Data, a pointer for the left child and a pointer for the right child. Let’s implement a tree in java.
/* Class containing left and right child of currentnode and key value*/class Node { int key; Node left, right; public Node(int item)
{
key = item; left = right = null; }
}
Simple Tree in Java
Let us create a simple tree with 4 nodes. The create tree would look like this.
class Node{ int key; Node left, right; public Node(int item) { key = item; left = right = null; }
}// A Java program to introduce Binary Treeclass BinaryTree{ // Root of Binary Tree Node root;
// Constructors BinaryTree(int key) {
root = new Node(key);
} BinaryTree() {
root = null;
} public static void main(String[] args) { BinaryTree tree = new BinaryTree(); /*create root*/ tree.root = new Node(1); /* following is the tree after above statement 1 / \ null null */ tree.root.left = new Node(2); tree.root.right = new Node(3); /* 2 and 3 become left and right children of 1 1 / \ 2 3 / \ / \ null null null null */
tree.root.left.left = new Node(4); /* 4 becomes left child of 2 1 / \ 2 3 / \ / \ 4 null null null / \ null null */}}
Below are the most common types of trees:
- Full Binary Tree
- Complete Binary Tree
- Perfect Binary Tree
- Balanced Binary Tree
- A degenerate (or pathological) tree
Full Binary Tree A Binary Tree is known as a Full Binary Tree when all the nodes have 0 or 2 children.
Complete Binary Tree A Binary Tree is a Complete Binary Tree if all the levels are completely filled except possibly the last level and the last level has all keys as left as possible
Perfect Binary Tree A tree is known as a Perfect Binary tree when all the nodes have 2 children and all the leave nodes are at the same level.
Balanced Binary Tree A binary tree is balanced if the height of the tree is O(Log n) where n is the number of nodes. For Example, the AVL tree maintains O(Log n) height by making sure that the difference between the heights of the left and right subtrees is at most 1. Red-Black trees maintain O(Log n) height by making sure that the number of Black nodes on every root to leaf path is the same and there are no adjacent red nodes. Balanced Binary Search trees are performance-wise good as they provide O(log n) time for search, insert and delete.
A degenerate (or pathological) tree is a Tree where every internal node has one child. Such trees are performance-wise same as the linked list.
Conclusion
In this article, we have seen the types of storage for the data structures like linear and non-linear and we have also created a sample binary tree in java. Finally, we learned about types of Binary trees.
