Important Pathsum Questions | Binary Trees | Amazon, Microsoft
Today we will learn some important coding interview questions of Binary Trees. Quick recap of what binary trees are : Binary trees are a hierarchical data structures in which each node has at most 2 children generally referred as left and right child. Each node in a binary tree has 3 important components. Any guesses?
Right! Each node contains these 3 important components :
- Node value
- Pointer to left child
- Pointer to right child
Now, let’s jump to the highly important questions of Binary Tree Data Structures🚀
Question 1:
Find sum of all the numbers that are formed from root to leaf paths in a binary tree.
Didn’t understand? No worries, we will understand by an example.
So, the question is pretty clear now! Now, all we have to do is write the function pathSum() which takes the root of the tree as input and returns the sum of numbers formed from paths root to leaf.
Would you like to complete the below function on your own? Try thinking the logic on your own first, then see my explanation.
Step 1:
Declare a global variable ans. Initialize it to 0. We will make a helper function that will do all the work for us.
Step 2:
Now all we have to do is write the helper method dfs(). I named the helper method as dfs() because we will be traversing deep into the tree as we do in Depth First Search (in short DFS is a technique to traverse/travel the entire binary tree).
💡 logic : while traversing the tree keep making the numbers from root to leaf (using val variable). If leaf node is encountered, add the val variable into global variable ans.
Complete Code
Question 2:
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Description is pretty clear. Here’s an example for you.
The logic of this question is very much similar to the previous question. Try to think in the same way.
If you face any problem in the second question, write in comments. I would love to help. Link of the question on leetcode. If you want me to explain the logic of 2nd question as well do write in comments.
