Mobile Apps Development

Data Structure: A Closer Look at Tree

September 08, 2020

Introduction to Tree Data Structure

There is an interesting data structure that has got its application in a wide number of scenarios in computer science. This data structure is Tree. Other data structures such as arrays, linked list, stack, and queue are linear data structures that store data sequentially.

To perform any operation in a linear data structure, the time complexity increases along with the increase in the data size (input data). But, it is not acceptable in today’s computational world since we have a lot of data to be processed.

Different tree data structures allow quicker and easier access to the data as it is a non-linear data structure.

But before getting into that, let’s ask ourselves a question.

Q: How should we decide which data structure to use?

Our choice of data structure depends upon several factors:

  • What needs to be stored? A certain data structure can be the best fit for a particular kind of data
  • Cost of operations. Quite often, we want to minimize the cost of most frequently performed operations
  • Memory consumption. Sometimes, we may want to minimize the memory usage
  • Easy of implementation.  We may also choose a data structure for ease of implementation, although this may not be the best strategy.

Q: What do we use Tree for?

Tree is one data structure that’s quite often used to represent hierarchical data. For example, let’s say we want to show employees in an organization and their positions in an organizational hierarchy, we can show it like this:

This particular logical structure in the image above is a Tree. If we look at this structure upside down and then it will resemble a real tree. The root here is at the top and we are branching out in a downward direction. The logical representation of the tree data structure is always like that. Root at the top and branching out in a downward direction.

=> Tree is an efficient way of storing and organizing data that is naturally hierarchical.

The tree data structure can be defined as a collection of entities called nodes linked together to simulate a hierarchy. Tree is a non-linear data structure. The topmost node in the tree is called the root of the tree. Each node will contain some data and this can be data of any type. In the image above, data is the name of the employee and their designation. We may have an object with two string fields to store that info.

Each node will contain some data and may contain a link or reference to some other nodes that can be called its children.

Various types of trees have been created throughout the past years, to suit certain apps and meet certain constraints or requirements. Some examples are binary search tree, B tree, red-black tree, splay tree, treap, AVL tree and n-ary tree. Let’s take a closer look at some of them.

Binary Search Trees

A binary search tree (BST), as the name indicates, is a binary tree where data is organized in a hierarchical structure. This data structure stores values in sorted order. A BinaryBinary Tree is a Tree in which each node can have at most 2 children.

Every node in a binary search tree comprises the four attributes.

  1. key: The value stored in the node.
  2. left: The pointer to the child on the left
  3. right: The pointer to the child on the right.
  4. p: The pointer to the parent node.

A binary search tree has a unique property that distinguishes it from other trees. This property is known as the binary-search-tree property.

Let assume that A is a node in a binary search tree.

  • If B is a node in the left subtree of A, then B.key ≤ A.key
  • If B is a node in the right subtree of A, then B.key ≥ A.key
data structure tree
Visual representation of Binary Tree

Application of tree in Computer science:

  • Storing naturally hierarchical data. For example, the files system in our computer disk driver are stored in the form of Tree. The file and folder hierarchy is naturally hierarchical data.
data structure tree
Example of Folder represented with ‘tree’ command in Mac OS
  • Organizing data for quick search, insertion, deletion. Example: Binary search trees can give us O(log n) time for searching an element in it. This is so fast and effective when we want to look for a specific element.
  • Trie: is a special kind of Tree used to store dictionaries. It’s really fast and efficient and is used for dynamic spell checking
  • Network Routing algorithm

Heaps

A Heap is a special case of a binary tree where the parent nodes are compared to their children with their values and are arranged accordingly.

Let us see how we can represent heaps. Heaps can also be represented using trees as well as arrays. The following images show us how we can represent a binary heap using a binary tree and an array.

data structure tree
Binary Tree representation of a Heap
Array Representation of a Heap

Heaps can be one of two types:

  1. Min Heap — the key of the parent is smaller than or equal to those of its children. This is known as the min-heap property. The root will contain the heap’s minimum value.
  2. Max Heap — the key of the parent is bigger than or equal to those of its children. This is known as the max-heap property. The root will contain the heap’s maximum value.

Applications of heaps

  • Can be used in a heapsort algorithm.
  • Can be used to implement priority queues as the priority values can be ordered according to the heap property where the heap can be implemented using an array.
  • Queue functions can be developed using heaps with O(log n) time complexity.
  • Can be used to find the kᵗʰ smallest (or biggest) value in a given array.

For more articles like this, just follow our Facebook, LinkedIn and Twitter. And here are some related articles for you:

Also published on

Share post on

Get in touch

Simply register below to receive our weekly newsletters with the newest blog posts