In this session let us tackle some interesting Tree based interview questions.

Prep Questions:

Here are some prep questions that focus on the core concepts:

  1. How to create a Binary Trees?
  2. How to traverse a binary tree? BFS, DFS (in-order, pre-order, post-order).
  3. What is a Binary Search Trees?
  4. How to insert into, deleting from, and searching BSTs
  5. How to find out if a tree is balanced or not?
  6. How to balance an unbalanced BST

Warm-up Questions

  1. Given a Binary Search Tree (BST), modify the find method to return the closest element in the BST if an exact match is not found.
  2. Given a Binary Search Tree (BST), find two numbers in the BST that add up to the given target.
  3. Given a post order traversal of a BST – reconstruct it.
    Example Input: 4, 12, 10, 18, 24, 22, 15, 31, 44, 35, 66, 90, 70, 50, 25

Workout Questions

Note: Path means the series of nodes from a “source” node to a “destination” node. and PathSum refers to the addition of values in each of the nodes in the path. This is generally applicable for trees/graphs with integer values at nodes or integer edge costs.

  1. Easy: Given a binary tree and a target sum. Find a path from “root” to “destination” such that the pathsum is equal to the target sum.
  2. Moderate: Given a binary tree and a target sum. Find a path from “any node” to “its child node” such that the pathsum is equal to the target sum.
  3. Moderate:Given a binary tree and a target sum. Find a path from “any node” to “any node” such that the pathsum is equal to the target sum. You must not visit the same node twice.
  4. Moderate: How will you optimize the algorithm, if all numbers in the tree are positive
  5. Moderate: What changes in your algorithm if the given tree is a binary search tree.
  6. Given the list of letters a-zA-Z0-9<space><period>, and their frequency. Implement huffman encoding.

Video

Comments

comments