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.