Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Non-Linear Data Structures
3.
Time Complexity
4.
Space Complexity
5.
Binary Tree
5.1.
Time Complexity
5.2.
Space Complexity
6.
Binary Search Trees:
6.1.
Time Complexity
6.2.
Space Complexity
7.
AVL Trees:
7.1.
Time Complexity
7.2.
Space Complexity
8.
Heap
8.1.
Time Complexity
8.2.
Space Complexity
9.
HashMap
9.1.
Time Complexity
9.2.
Space Complexity
10.
Trie
10.1.
Time Complexity And Space Complexity: 
11.
N-ary Tree
11.1.
Time Complexity
12.
Average time complexity:
13.
Worst time complexity:
14.
FAQs
15.
Key Takeaways
Last Updated: Mar 27, 2024

Time and Space Complexity of Non-Linear Data Structures

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

The most important thing for interviews in product-based companies is data structures. The data structure is a way of storing and organizing the available data for further use. Data structures are of two types, Linear and Non-linear. Let us discuss non-linear data structures and their complexity.

Non-Linear Data Structures

Non - Linear Data Structures are those Data Structures in which data is not stored linearly or sequentially, and due to which each element is not connected to the previous or next element so that they can be accessed in a single run. Non-linear data structures are more complex and memory-efficient with respect to linear data structures.

Some examples of non-linear data structures are trees, graphs, etc.

Let us discuss their time and space complexity and Rabin Karp Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Time Complexity

Time complexity can be understood as a concept that constitutes the quantification of time taken by an algorithm or code snippet to execute. The time complexity is also a measure of the efficiency, such that the lesser the time is taken by the algorithm, the more its efficiency will be. 

We will be discussing only the worst-case time complexity in this article.

Space Complexity

Space Complexity can be understood as the amount of memory space occupied by a code snippet or algorithm. It is one of the two measures of the efficiency of an algorithm. The lesser the space it takes, the more efficient it is.

Now let’s discuss the complexities of some non-linear Data structures.

Binary Tree

A tree in which all the nodes do not have more than two children is called a Binary Tree.

For Example: 

For a binary tree consisting of N nodes:

Time Complexity

  • The time complexity for accessing any specific node:
    • Average Complexity: O(log N)
    • Worst Complexity: O(N)
       
  • The time complexity for searching any specific node:
    • Average Complexity: O(log N)
    • Worst Complexity: O(N)
       
  • The time complexity for inserting any specific node:
    • Average Complexity: O(log N)
    • Worst Complexity: O(N)
       
  • The time complexity for deleting any specific node:
    • Average Complexity: O(log N)
    • Worst Complexity: O(N)

Space Complexity

For all the operations, no extra space is required, thus the space complexity will be O(1).

 

Also see, Morris Traversal for Inorder, hash function in data structure.

Binary Search Trees:

The first word of ‘Binary Search Trees’, namely ‘Binary’, tells us that every node in the tree can have at most two children, the left child, and the right child. The data of the right child and the left child must be greater and smaller than the data of the parent node, respectively.

Lets us see an example of a binary search tree.

For a binary search tree consisting of N nodes:

Time Complexity

  • The time complexity for accessing any specific node:
    • Average Complexity: O(log N)
    • Worst Complexity: O(N)
       
  • The time complexity for searching any specific node:
    • Average Complexity: O(log N)
    • Worst Complexity: O(N)
       
  • The time complexity for inserting any specific node:
    • Average Complexity: O(log N)
    • Worst Complexity: O(N)
       
  • The time complexity for deleting any specific node:
    • Average Complexity: O(log N)
    • Worst Complexity: O(N)

Space Complexity

For all the operations, no extra space is required, thus the space complexity will be O(1).

Read More - Time Complexity of Sorting Algorithms And Application of Graph in Data Structure

AVL Trees:

For an AVL tree consisting of N nodes:

Time Complexity

  • The time complexity for accessing any specific node:
    • Average Complexity: O(logN)
    • Worst Complexity: O(log(N))
       
  • The time complexity for searching any specific node:
    • Average Complexity: O(logN)
    • Worst Complexity: O(logN)
       
  • The time complexity for inserting any specific node:
    • Average Complexity: O(logN)
    • Worst Complexity: O(logN)
       
  • The time complexity for deleting any specific node:
    • Average Complexity: O(logN)
    • Worst Complexity: O(logN)

Space Complexity

For all the operations, no extra space is required, thus the space complexity will be O(1).

Heap

For a heap consisting of N nodes:

Time Complexity

  • The time complexity for finding the minimum / maximum value node is
    • Average Complexity: O(1)
    • Worst Complexity: O(1)
       
  • The time complexity for inserting a node is
    • Average Complexity: O(log N)
    • Worst Complexity: O(log N)
       
  • The time complexity for deleting the minimum / maximum value node is
    • Average Complexity: O(log N)
    • Worst Complexity: O(log N)
       
  • The time complexity for extracting the minimum / maximum value node is
    • Average Complexity: O(log N)
    • Worst Complexity: O(log N)
       
  • The time complexity to search/delete any node is
    • Average Complexity: O(N)
    • Worst Complexity: O(N)

Space Complexity

For all the operations, no extra space is required, thus the space complexity will be O(1).

HashMap

For a hash map consisting of N values:

Time Complexity

  • The time complexity to insert a value is
    • Average Complexity: O(1)
    • Worst Complexity: O(1)
       
  • The time complexity to delete a value is
    • Average Complexity: O(1)
    • Worst Complexity: O(1)
       
  • The time complexity to resize the map is
    • Average Complexity: O(1)
    • Worst Complexity: O(1)
       
  • The time complexity to hash a value is
    • Average Complexity: O(1)
    • Worst Complexity: O(1)

Space Complexity

For all the operations, no extra space is required, thus the space complexity will be O(1).

Trie

A trie is considered to be a data structure used to store strings, in a manner such that, strings that have common prefixes share an ancestor.  

Time Complexity And Space Complexity: 

The space complexity for the creation of the trie is O(alphabet_size * average key length * N).

For different operations in a Trie, the average and worst time complexities are the same. 

  • Insertion: 

    For a string of length ‘N’ to be inserted in the trie:

  • Time Complexity: O(N), since we need to perform ‘N’ iterations.
  • Space Complexity: O(N), since ‘N’ new nodes will be added which will occupy space up to O(N).
     
  • Deletion:

    For a string of length ‘N’ to be deleted from the trie:

  • Time Complexity: O(N), since we will have to traverse down the whole tree to reach the leaf node to delete.
  • Space Complexity: O(1), as no extra space would be used. 
     
  • Searching:

    For a string of length ‘N’ to be searched from the trie:

  • Time Complexity: O(N), since we will have to traverse down the length of the string, to trace it.
  • Space Complexity: O(1), as no extra space would be used.

N-ary Tree

N-ary trees also known as generic trees are trees in which every node has many children, and the number of children may not be known in advance.

Time Complexity

The time complexity for different operations in an N-ary tree is as follows:

  • Searching: 
    • Time Complexity: O(N), where N is the maximum(worst) number of iterations to find a value at the last iteration.
       
  • Addition of new node: 
    • Time Complexity: O(N), as we have for statement and no nested loops.

Average time complexity:

Data Structure Insert Delete Access Search
Binary Tree O(log N) O(log N) O(log N) O(log N)
Binary Search Tree O(log N) O(log N) O(log N) O(log N)
AVL Tree O(log N) O(log N) O(log N) O(log N)
Heap O(log N) O(N) O(log N), for accessing min/max element O(N)
Trie O(N) O(N) - O(N)
N-ary Tree O(N) - - O(N)

Worst time complexity:

Data Structure Insert Delete Access Search
Binary Tree O(N) O(N) O(N) O(N)
Binary Search Tree O(N) O(N) O(N) O(N)
AVL Tree O(log N) O(log N) O(log N) O(log N)
Heap O(log N) O(N) O(log N), for accessing min/max element O(N)
Trie O(N) O(N) - O(N)
N-ary Tree O(N) - - O(N)

Must Read Algorithm Types

Also read - Data Structure MCQ

FAQs

  1. What is a Data structure?
    A data structure is a way of storing data and organizing it, so that it is easier to use the information stored efficiently, change, add more of it or delete any. In different programs, we use different data structures based on the requirements of the operations further.
     
  2. What are non-linear data structures?
    Linear Data Structures are those data structures in which data is stored sequentially, and each element is connected to the previous or next element so that they can be accessed in a single run. Some examples of linear data structures are arrays, stacks, queues, etc.
     
  3. Among linear and non-linear data structures, which one is more memory efficient?
    Non-linear data structures are more memory efficient than linear data structures but this efficiency increases the complexity of non-linear data structures.
     
  4. What is time complexity?
    Time complexity can be understood as a concept that constitutes the quantification of time taken by an algorithm or code snippet to execute. The time complexity is also a measure of the efficiency, such that the lesser the time is taken by the algorithm, the more its efficiency will be.
     
  5. What is space complexity?
    Space Complexity can be understood as the amount of memory space occupied by a code snippet or algorithm. It is one of the two measures of the efficiency of an algorithm. The lesser the space it takes, the more efficient it is.

Key Takeaways

In the above article, we learned about the time and space complexity of Non-Linear Data Structures, which is a very important concept required in the preparation for all the DSA based interviews. 

You can also consider our Online Coding Courses such as the DSA in PythonC++ DSA CourseDSA in Java Course to give your career an edge over others.

 Keep practicing and growing.

Previous article
Time and Space Complexity of Linear Data Structures
Next article
Recursion & Backtracking Time Complexity
Live masterclass