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:

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

### Warm-up Questions

- 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.
- Given a Binary Search Tree (BST), find two numbers in the BST that add up to the given target.
- 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.

- 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.
- 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.
- 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.
- Moderate: How will you optimize the algorithm, if all numbers in the tree are positive
- Moderate: What changes in your algorithm if the given tree is a binary search tree.
- Given the list of letters a-zA-Z0-9<space><period>, and their frequency. Implement huffman encoding.