Binary Trees — A Complete Guide

You must have studied about the various Linear Data Structures till now like Arrays, Strings, Linked-Lists, etc. As you know in them, the data is arranged in a sequence and they follow some kind of order for the arrangement of data. But now things are going to change as we move on to non-linear data structures. In these non-linear data structures the data is not organised in any sort of sequence, its place randomly throughout the respective data structure.The non-linear data structures are multi-level whereas the linear data structures were a uni-level data structure only.

So the first non-linear data structure that we are going to talk about is a binary tree , which is a special type of a tree data structure

Enough of the introduction now let's get straight to the point for the reason why you are here.

So a binary tree is a type of a tree data structure in which every node has at maximum two children and minimum 0 child nodes that is it has either 2 child nodes or 1 child node or no child node at all. The node is sometimes referred to as a Vertex in some cases too.

Want to read this story later? Save it in Journal.

Let’s understand about some basic definitions first which are required to understand the working of a binary tree.

A Node is a place where we store data in a Tree. It has references to point to its child nodes or get pointed from the parent nodes.

A Subtree represents the Descendents of a node

A parent node is the node , to which the two child nodes are connected to and there reference is present in the parent node only.

Levels are also an important term to understand what a tree does . They are basically used to represent the generation of a node.For example:- say the root node is present at the level 0, child node is present at level-1 and the grandchild node is present at a level 2 and so on.

A Leaf node is a node which doesn't have any child node.

A Root node is a node which is present at the topmost level of a tree , this node doesn't have any parent node.

So these child nodes which a node has, are present lower to the parent node(just for visualisation), the node present on the left side of its parent node is called as the left child node and the node present on the right side of its parent node is called as a right child node.

Traversal of nodes means moving through the nodes in a specific order.

Sibling nodes in a tree are those which have the same parent node and are present at the same level.

All the nodes in the tree have a Key value for which we perform various operations, to alter those key values of specific nodes.Keys are sometimes also called as Data of that node.

For better understanding you can refer the image below.

Binary Tree representation with keywords

There are two ways to represent a tree first is using Arrays and Second is using Linked Lists. But we generally use Linked lists to represent tree since they are a lot more efficient for performing operations.

Code wise we make a class with different instances of it which represents the various properties of the tree. Here we take the example of the code snippet in Java:-

private class Node {
int data;
Node left;
Node right;

Node(int data, Node left, Node right) {
this.data = data;
this.left = left;
this.right = right;
}
}

Applications Of Binary Tree

Binary trees are vastly used to represent a non-linear data structure. There are various forms of Binary Trees. Binary trees play a very import role in software-related applications. One of the applications of a Binary Tree is that it used in the searching algorithms. They are also used to store hierarchical data like folder structure, HTML data, etc. They are also used for compositing digital images for visual effects. Also, binary trees are used to implement various other data structures like Binary Search Tree, Heaps, Tries, K-D tree, Spanning trees, etc.

Types Of Binary Trees

1. Full Binary Tree
2. Complete Binary Tree
3. Extended Binary Tree
4. Threaded Binary Tree

For the traversal in a tree, we have three Types Of Traversal techniques and they are:-

1. Pre-Order Traversal (Parent Node, Left Child, Right Child)
2. Inorder Traversal (Left Child, Parent Node, Right Child)
3. Post-Order Traversal (Left Child, Right Child, Parent Node)

There are various Operations that we can perform on trees such as :-

1. Finding the maximum node.
2. Finding the minimum node.
3. Finding the height of a tree.
4. Finding the size of a tree.
5. Finding the mirror tree.
6. Finding the Pre-order, Post-Order and In-order of a tree.

And a lot more, you can practice them to understand the concepts more clearly.I will share with you the code snippet to find the maximum of a tree and height of the tree.

Code Snippet To Find The Maximum Node:-

public int max() {
return this.max(this.root);
}

private int max(Node node) {
if (node == null) {
return Integer.MIN_VALUE;
}

int lmax = this.max(node.left);
int rmax = this.max(node.right);
int myans = Math.max(lmax, Math.max(rmax, node.data));
return myans;
}

Code Snippet To Find The Height Of A Tree:-

public int height() {
return this.height(this.root);
}

private int height(Node node) {
if (node == null) {
return -1;
}

int lheight = this.height(node.left);
int rheight = this.height(node.right);
int myans = Math.max(lheight, rheight) + 1;
return myans;
}

Hope you would have understood the about all the basics of tree and would be a lot more confident about it.We will discuss about various other Non-Linear data structures.Till then stay safe and keep practicing.

Also please do clap this article if you liked my work.

References:

Binary Trees

Data Structure and Algorithms - Tree

📝 Save this story in Journal.

👩‍💻 Wake up every Sunday morning to the week’s most noteworthy stories in Tech waiting in your inbox. Read the Noteworthy in Tech newsletter.