Tree Data Structure

Till now we have explored various data structures such as Arrays and Linked lists. Today we are going to take a deep dive into the Tree data structure. If you haven’t already read my previous articles on Pointers, check them and come back.

All you need to know about Pointers -Part-1

All you need to know about Pointers-Part-2

What is a tree data structure ?

A tree is a non-linear hierarchical data structure that has its applications in various areas. The top most node in a tree is called root. The left branch is called left subtree and the right is called right subtree. Each node that has children is called a parent node.

A tree looks like this:

Courtesy: Geeks for Geeks

From the above diagram, we can see that 1 is the root of the tree. 2 and 3 are child nodes of parent 1 and are themselves parents for 4, 5 and 6, 7 respectively. The nodes 8, 9, 10, 11, 13, 14 are called leaf nodes.

Why Trees ?

1. We need to use a tree data structure when we want to store information that forms a hierarchy. An excellent example would be file system on a computer.
2. Accessing elements of a tree is faster than Linked lists but still slower than arrays.

Some applications of trees include:

1. Indexing in Databases.

2. Routing algorithms

3. Syntax analysis in Compilers

Binary Trees

The most common tree used in wide variety of applications is the Binary Tree. A binary tree is a tree in which each parent has at most 2 children viz., the left and the right child. A tree is represented as a hierarchical connection of nodes and each node consists of following parts:

1. Data
2. Pointer to the left child
3. Pointer to the right child

The above diagram shows the structure of the tree in memory.

Now let us see how can we implement a binary tree data structure. The language that will be used throughout the demo is C++. First step is to create a node.

Now let us create the tree structure using the above Node class.

Now, how do we access the elements or traverse through the elements of the tree. We have 3 traversal methods to accomplish this task.

1. In-order traversal
2. Pre-order traversal
3. Post-order traversal

In-order traversal

In this type of traversal, we first traverse the left subtree, then visit the root and then traverse the right subtree.

Pre-order traversal

In this type of traversal, we first visit the root, then traverse the left subtree and then traverse the right subtree.

Post-order traversal

In this type of traversal, we first traverse the left subtree, then traverse the right subtree and then visit the root.

Binary Search Trees

Now, let us look at a special kind of Binary tree called the Binary Search Tree (BST). A binary tree can qualify to be a BST if it satisfies the following conditions:

1. The left subtree of a node contains only nodes with keys lesser than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. The left and right subtree each must also be a binary search tree.

Let us see the implementation.

We can see from the above class definition that there are 3 member functions viz., insert(), contains() and printInorder(). The contains() method is used to check or search for a particular key in the BST.

Insertion of nodes must happen in such a way without disturbing the properties of BST. Let us see how insertion is done.

The contains() method checks for the presence of a particular key in the BST. It returns a boolean value stating whether the element was found or not.

We make use of in-order traversal to access and print the elements of the tree.

The sample code to test the working of these methods is given below:

Exercise:

1. As an exercise, try to implement a delete function that would delete the specified element from the BST.

Hope you enjoyed reading the article!

If you have any queries please post in the comment section below. Connect with me on LinkedIn . Also, if you want to look at my amazing collection of apps developed, don’t forget to check Google Play Store.

Know more about me here.

With that being said, thanks for reading my article and Happy Coding!