Questions
13 of 26
1What is a Tree? Define Node, Root, Leaf, Edge, Height, Depth.
2What is a Binary Tree?
3What is a Binary Search Tree (BST)? What are its properties?
4What is the difference between a Binary Tree and a Binary Search Tree?
5Explain Tree Traversals: Inorder, Preorder, Postorder, Level Order.
6How do you implement Inorder traversal iteratively? (Without recursion)
7How do you find the Lowest Common Ancestor (LCA) of two nodes in a BST?
8How do you validate if a given Tree is a valid BST?
9What is a Balanced Tree? Why do we need balance?
10What is a Complete Binary Tree? A Full Binary Tree? A Perfect Binary Tree?
11What is a Heap? (Min-Heap and Max-Heap)
12How is a Heap implemented using an Array? (Parent/Child index math)
13What is the time complexity of insertion and deletion in a Heap? Why?
14What is Heapify? Explain the process.
15What is a Trie (Prefix Tree)? When is it used?
16How does a Trie compare to a Hash Table for string storage?
17What is an AVL Tree? What is a Red-Black Tree? What is the difference?
18Why do databases prefer B-Trees/B+ Trees over Binary Search Trees?
19How do you serialize and deserialize a Binary Tree?
20What is a Segment Tree? What problems does it solve?
21What is a Fenwick Tree (Binary Indexed Tree)?
22What is the difference between a B-Tree and a B+ Tree? Why are B+ Trees better for disk access?
23Explain the concept of Tree Rotation.
24What is a Splay Tree? When would you use it?
25How do you find the diameter of a Binary Tree?
26How do you check if a tree is symmetric (Mirror image)?
Data-StructuresData-Structures
Basics
Complexity Analysis
Arrays and Strings
Linked Lists
Stacks and Queues
Hash Tables
Trees
Graphs
13 / 26

What is the time complexity of insertion and deletion in a Heap? Why?

Difficulty: 3/10

Heap Operation Complexity

Heap insertion takes O(log n) because the new element is initially placed at the end and may bubble up along the height of the heap. Removing the root also takes O(log n): the last element replaces the root and is then sifted down. Since a heap is complete, its height is O(log n).

javascript
  1. 1

    Peek: O(1).

  2. 2

    Insertion: O(log n).

  3. 3

    Delete-min/delete-max: O(log n).

  4. 4

    Search for an arbitrary value: O(n) in the general case.

  5. 5

    Heap height is O(log n) because the tree is complete.

Follow-up Questions

  • Why is arbitrary search O(n)?
  • What is the complexity of building a heap from n elements?
Share

Share via WhatsApp, X, Facebook, LinkedIn or copy link. Open Graph preview enabled.