Questions
15 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
15 / 26

What is a Trie (Prefix Tree)? When is it used?

Difficulty: 4/10

Trie

A Trie, or prefix tree, stores strings character by character along paths from the root. Nodes represent prefixes, and terminal markers identify complete words. Tries are useful when prefix operations are important, such as autocomplete, dictionary lookup, spell checking, routing tables, and prefix-based search.

javascript
  1. 1

    Insert a string of length L: O(L).

  2. 2

    Search a string of length L: O(L).

  3. 3

    Prefix search: O(P), excluding output traversal.

  4. 4

    Performance depends on alphabet representation and memory usage.

  5. 5

    Tries are especially effective for autocomplete and prefix queries.

Follow-up Questions

  • How would you reduce Trie memory consumption?
  • How would you implement autocomplete using a Trie?
Share

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