Skip to main content

Tree Introduction

Here are some important topics related to trees that are commonly covered in technical interviews:

  1. Tree representation: How to represent a tree in memory, including array and linked list representations.
  2. Tree traversal: How to traverse a tree, including in-order, pre-order, and post-order traversals.
  3. Binary search tree: How to implement and maintain a binary search tree, including insertion, deletion, and search operations.
  4. Heap: How to implement and maintain a heap, including insertion, deletion, and heapify operations.
  5. Red-black tree: How to implement and maintain a red-black tree, including insertion, deletion, and search operations.
  6. Trie: How to implement and maintain a trie, including insertion, deletion, and search operations.
  7. Huffman coding tree: How to construct a Huffman coding tree for data compression.
  8. Segment tree: How to implement and maintain a segment tree, including construction, query, and update operations.
  9. Fenwick tree (Binary Indexed Tree): How to implement and maintain a Fenwick tree, including construction, query, and update operations.
  10. AVL tree: How to implement and maintain an AVL tree, including insertion, deletion, and search operations.

Standard Tree Problems​

  • height of a tree
  • diameter of a tree
  • size of a tree
  • lowest common ancestor

It's also helpful to be familiar with various types of trees, such as binary trees, n-ary trees, and balanced and unbalanced trees.

Topics Covered​