This was yesterday's POTD, missed this cause I was late with other things that I had to finish, although I had seen the problem and also got the idea and was pretty sure that this idea would be working, but didn't have time to implement.
Had contemplated about my productivity, and that led to a previously received advice, to divide my priorities in a weekly basis too cause I felt that I was focusing on daily priorities but wasn't able to completely give time to the things that I wanna invest time for, in a proper planned manner.
So just experimenting with things, trying to normalise the new plannings, just need to continue this consistently, and... blogging was in a pause, but I have decided that I will be having like 3 blogs per week in which will try to explain some programming concept most probably. I can continue with just 1 prob or concept per day considering that I have most of the concepts that are needed for competitive prog, so that's the part for programming, just gotta stay in touch.
This Vertical Sum problem was interesting, although the idea struck my mind in just a few minutes of thinking cause had the concept and the visualisation of recursion in my mind since I have solved many variations of problems in trees, graphs and also the standard problems are there, which I had studied to understand their nature of working, such questions become easy only under our own steam, cause there might be cases where we can relate these to some other types of problems but not focusing on the base concepts will have it's ramifications.
The idea of the problem is mentioned in the code itself.
Problem Statement:-
Given a binary tree having n nodes, find the vertical sum of the nodes that are in the same vertical line. Return all sums through different vertical lines starting from the left-most vertical line to the right-most vertical line.
Example 1:
Input:
1
/ \
2 3
/ \ / \
4 5 6 7
Output:
4 2 12 3 7
Explanation:
The tree has 5 vertical lines
Line 1 has only one node 4 => vertical sum is 4.
Line 2 has only one node 2 => vertical sum is 2.
Line-3 has three nodes: 1,5,6 => vertical sum is 1+5+6 = 12.
Line-4 has only one node 3 => vertical sum is 3.
Line-5 has only one node 7 => vertical sum is 7.
Example 2:
Input:
1
/
2
/
3
/
4
/
6
/
7
Output:
7 6 5 4 3 2 1
Explanation:
There are seven vertical lines each having one node.Your Task:
You don't need to take input. Just complete the function verticalSum() that takes root node of the tree as parameter and returns an array containing the vertical sum of tree from left to right.
Expected Time Complexity: O(nlogn).
Expected Auxiliary Space: O(n).
Constraints:
1<=n<=104
1<= Node value <= 105
Code Implementation:-
class Solution:
def __init__(self):
self.ans=[]
self.offsets=dict()
# whenever we'll go to left, will decrease offset by 1, on goin to right
# will increase by 1, and will add all the elems at the same offset
def helpFunc(self,root,offset):
if(root!=None):
if(offset in self.offsets.keys()):
self.offsets[offset]+=root.data
else:
self.offsets[offset]=0
self.offsets[offset]+=root.data
self.helpFunc(root.left,offset-1)
self.helpFunc(root.right,offset+1)
#Complete the function below
def verticalSum(self, root):
'''
Just traversing the tree using recursion, on goin left, offset-=1
and on goin right offset+=1, so the elems which will be in the same
line will be having offsets same and thus will keep adding the elems
in the same lines, at the end sorting the summation based on the lines
from leftmost to rightmost line summation and returning in that order
Can print things if any confusion.
'''
self.ans=[]
self.helpFunc(root,0)
# whatever summations we have for various offsets(lines)
# getting them in sorted order leftmost line to rightmost line
data=sorted(list(zip(self.offsets.items())))
self.ans=[elem[0][1] for elem in data]
return self.ans
And today's POTD:-
If you have got enough practice with tree traversing and a little bit understanding of recursive calls then you can easily solve this one.
Problem Statement:
Given a Binary Tree of n nodes, find all the nodes that don't have any siblings. You need to return a list of integers containing all the nodes that don't have a sibling in sorted order (Increasing).
Two nodes are said to be siblings if they are present at the same level, and their parents are the same.
Note: The root node can not have a sibling so it cannot be included in our answer.
Example 1:
Input :
37
/
20
/
113
Output:
20 113
Explanation:
Nodes 20 and 113 dont have any siblings.
Example 2:
Input :
1
/ \
2 3
Output:
-1
Explanation:
Every node has a sibling.Your Task:
You don't need to read input or print anything. Complete the function noSibling() which takes the root of the tree as input parameter and returns a list of integers containing all the nodes that don't have a sibling in sorted order. If all nodes have a sibling, then the returning list should contain only one element -1.
Expected Time Complexity: O(nlogn)
Expected Auxiliary Space: O(Height of the tree)
Constraints:
1 ≤ n ≤ 104
Code Implementation:
def util(root,ansList):
# Just traverse the whole tree and check for nodes with no siblings
if(root!=None):
if(root.left!=None and root.right==None):
ansList.append(root.left.data)
elif(root.left==None and root.right!=None):
ansList.append(root.right.data)
util(root.left,ansList)
util(root.right,ansList)
return ansList
def noSibling(root):
# code here
ans=sorted(util(root,[]))
if(len(ans)==0):
return [-1]
else:
return ans
Comments
Post a Comment