Non-Linear Data Structures: Interview Questions & Answers
for Freshers
Trees, Binary Search Trees, Graphs, Heaps & Hash Tables
1. Trees & Binary Search Trees (BST)
Q1. What is a Non-Linear Data Structure and how does it differ from a Linear Data Structure?
In a Linear Data Structure (like Arrays, Linked Lists, Stacks, Queues), elements are arranged sequentially
one after another. In a Non-Linear Data Structure (like Trees, Graphs), elements are not arranged
sequentially; instead, they are connected hierarchically or as a network of nodes, allowing multiple
paths to traverse elements.
Q2. What is a Tree Data Structure and what are its core terminologies?
A Tree is a hierarchical non-linear data structure consisting of nodes connected by edges.
Core Terminologies:
• Root: The top-most node of the tree (has no parent).
• Parent & Child: A node directly connected above another is the parent; the node below is the child.
• Leaf Node: A node that has no children.
• Subtree: A tree formed by a node and all of its descendants.
• Height of Tree: The maximum number of edges from the root node to a leaf node.
• Depth of Node: The number of edges from the root node to that specific node.
Q3. What is a Binary Tree?
A Binary Tree is a tree structure where each node can have at most two children, typically referred to as
the Left child and the Right child.
Q4. What are the different types of Binary Trees?
• Full Binary Tree: Every node has either 0 or 2 children (no node has only 1 child).
• Complete Binary Tree: All levels are completely filled except possibly the last level, which is filled from
left to right.
• Perfect Binary Tree: All internal nodes have two children and all leaf nodes are at the exact same level.
• Balanced Binary Tree: The height difference between the left and right subtrees of any node is at most
1.
Q5. What is a Binary Search Tree (BST)? What is its main property?
A Binary Search Tree (BST) is a node-based binary tree data structure with a specific ordering property:
• The value of all nodes in the Left Subtree is strictly smaller than the parent node's value.
• The value of all nodes in the Right Subtree is strictly greater than the parent node's value.
Property: Left Subtree < Root < Right Subtree.
Q6. What are the time complexities for Search, Insertion, and Deletion in a BST?
• Average Case: O(log N) time complexity for Search, Insertion, and Deletion because half the tree is
eliminated at each step.
• Worst Case: O(N) time complexity when the tree becomes unbalanced/skewed (resembling a linked
list, e.g., inserting numbers 1 -> 2 -> 3 -> 4 sequentially).
Q7. What are the standard Tree Traversal techniques?
Tree traversals visit all nodes in a specific order:
1. In-Order Traversal (Left, Root, Right): Visits left child, root, then right child. (Note: Performing In-Order
traversal on a BST yields elements in sorted ascending order).
2. Pre-Order Traversal (Root, Left, Right): Visits root first, then left child, then right child. Useful for
creating a copy of a tree.
3. Post-Order Traversal (Left, Right, Root): Visits left child, right child, then root. Useful for deleting a
tree from bottom to top.
4. Level-Order Traversal (BFS): Visits nodes level by level from top to bottom, left to right, using a Queue.
2. Graphs
Q8. What is a Graph Data Structure?
A Graph is a non-linear data structure consisting of a set of Vertices (or Nodes) and a set of Edges that
connect pairs of vertices. It is written as G = (V, E).
Q9. What is the difference between a Tree and a Graph?
• A Tree is a hierarchical structure with a single root node and exactly one path between any two nodes.
It cannot contain cycles/loops.
• A Graph is a network structure with no root node, can have multiple paths between vertices, and can
contain cycles or disconnected components.
Q10. What are the main types of Graphs?
• Directed Graph (Digraph): Edges have directions (e.g., A -> B means you can travel from A to B, but not
B to A).
• Undirected Graph: Edges are bidirectional (e.g., A - B means travel is allowed in both directions).
• Weighted Graph: Edges have numerical weights or costs associated with them (e.g., distance between
cities).
• Cyclic vs. Acyclic Graph: A cyclic graph contains at least one loop/path that starts and ends at the same
vertex.
Q11. How are Graphs represented in memory?
The two most common representations are:
1. Adjacency Matrix: A 2D grid/array of size V x V where matrix[i][j] = 1 indicates an edge between vertex
i and vertex j.
• Space Complexity: O(V^2)
• Best for: Dense graphs with many edges.
2. Adjacency List: An array of linked lists/vectors where list[i] contains all vertices directly connected to
vertex i.
• Space Complexity: O(V + E)
• Best for: Sparse graphs with fewer edges.
Q12. What are the two main Graph Traversal algorithms?
1. Breadth-First Search (BFS):
• Explores nodes level-by-level (outward from start vertex).
• Uses a Queue data structure and a Visited array.
• Used for finding the shortest path in unweighted graphs.
2. Depth-First Search (DFS):
• Explores as deep as possible along each branch before backtracking.
• Uses Recursion (or an explicit Stack) and a Visited array.
• Used for cycle detection, topological sorting, and solving mazes.
Q13. What is Dijkstra's Algorithm?
Dijkstra's Algorithm is a greedy algorithm used to find the shortest path from a single source vertex to all
other vertices in a weighted graph with non-negative edge weights. It uses a Priority Queue (Min-Heap)
to select the unvisited vertex with the smallest distance.
3. Heaps Data Structure
Q14. What is a Heap Data Structure?
A Heap is a specialized tree-based data structure that satisfies the Complete Binary Tree property and
the Heap Property.
Q15. What are the two types of Heaps?
1. Max-Heap: The value of the parent node is always greater than or equal to the values of its children.
The largest element is at the root.
2. Min-Heap: The value of the parent node is always smaller than or equal to the values of its children.
The smallest element is at the root.
Q16. How is a Binary Heap represented as an Array?
Because a Heap is a complete binary tree, it can be efficiently stored in a 0-indexed contiguous Array
without using pointers:
For a node at index i:
• Left Child index = 2*i + 1
• Right Child index = 2*i + 2
• Parent index = (i - 1) // 2
Q17. What are the time complexities of Heap operations?
• Get Min/Max (Peek): O(1)
• Insert element: O(log N)
• Delete Min/Max (Extract): O(log N)
• Build Heap from an unsorted array: O(N)
4. Hash Tables & Hashing
Q18. What is a Hash Table and how does Hashing work?
A Hash Table is a data structure that stores key-value pairs. It uses a mathematical Hash Function to
compute an index/slot in an array where the value is stored, enabling average time complexity of O(1)
for lookup, insertion, and deletion.
Q19. What is a Hash Collision?
A Hash Collision occurs when a hash function maps two different input keys to the exact same array
index.
Q20. What are the common methods to resolve Hash Collisions?
1. Separate Chaining (Open Hashing): Each array index stores a Linked List or Bucket. When collisions
occur, new elements are simply appended to the list at that index.
2. Open Addressing (Closed Hashing): All elements are stored inside the array itself. If a collision occurs,
it searches for another empty slot using probing:
• Linear Probing: Checks index + 1, index + 2, index + 3 sequentially.
• Quadratic Probing: Checks index + 1^2, index + 2^2, index + 3^2.
• Double Hashing: Uses a second hash function to calculate the step size.