C# Interview with a Microsoft engineer.

C# Interview with a Microsoft Engineer: Sum Root to Leaf Numbers

Watch someone solve the sum root to leaf numbers problem in an interview with a Microsoft engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type
Sum Root to Leaf Numbers

Interview question
You are given the root of a binary tree containing digits from 0 to 9 only.
Each root-to-leaf path in the tree represents a number.
For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.
Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

Read more about the questions

Interview Feedback

Feedback about Recursive Snow (the interviewee)

Advance this person to the next round?
Yes

How were their technical skills?
4/4

How was their problem solving ability?
4/4

What about their communication ability?
4/4

Top 3 strongest performances I have seen on this platform. This was absolutely excellent. This was a medium and a hard question all solved in 45 mins. No negative feedback on this really. Absolutely excellent work.

Feedback about The Legendary Avenger (the interviewer)

Would you want to work with this person?
Yes

How excited would you be to work with them?
4/4

How good were the questions?
4/4

How helpful was your interviewer in guiding you to the solution(s)?
4/4

N/A

Interview Transcript

The Legendary Avenger: Hello.
Recursive Snow: Hello.
The Legendary Avenger: Hey, hope you're doing well. How's your day going?
Recursive Snow: My day is going fine.
The Legendary Avenger: Awesome. All right, so just to get us started, maybe give me a quick overview of what you're prepping for as well as what you're looking to get out of this, at least in this context given it's Microsoft. Maybe also give me a sense of the teams and all that. I might be able to have specific questions to help you.
Recursive Snow: Okay. I'm just mainly doing an interview practice session just to keep fresh on technical interviews for programming. That's primarily all there is at this point. I don't have any interviews currently scheduled. I just want to make sure that I'm up on keeping practice with stuff like this.
The Legendary Avenger: I see what you're saying.
Recursive Snow: Okay.
The Legendary Avenger: And how much experience do you have with these good type questions or coding interview type questions?
Recursive Snow: I have a decent amount of experience with these questions. I've had a few of these practice interviews in the past and I've also spent quite a bit of time working on questions like these on my own.
The Legendary Avenger: I see, okay, that's good. And so given at least your own practice, do you have a sense of, let's say, a specific type of pattern that you struggle with? That way we can at least focus on that rather than give you something that you're already good at.
Recursive Snow: I can't think of anything in particular now.
The Legendary Avenger: Okay, sounds good. Okay then. Cool. Then I'm just going to carry my Heuristic again. I'm going to use what I have observed at Microsoft. So there usually is a tendency towards array problems as well as tree problems. And I feel like tree problems might be something worth exploring at the moment, especially since I feel like the practice is set up and travaso is usually a good thing. So maybe you can focus on that. Are you okay with that?
Recursive Snow: Sure.
The Legendary Avenger: Awesome. All right, so you're going to select the language you want to use?
Recursive Snow: Which language we're going to use of what you said?
The Legendary Avenger: Yeah, feel free to select the language. You can switch it up at the top. Awesome. All right, so interesting, it's been a while since I used to C sharp in this case, but that's cool. So what we're going to do here is we are going to try and solve this particular problem here. So you'll be given a tree and what I want you to return is the maximum sum of leaves from the left to the right. So let me actually comment this out here. I know the syntax of commenting in C sharp actually. Okay, that works. So the whole idea here is if you're given a tree like this so let's say this is our lift node here and let's say we have two right here, maybe five. And maybe here it's in this case, the maximum sum from root to leave will be basically two plus five plus ten. So that should be 17.
Recursive Snow: Yeah.
The Legendary Avenger: Does it make sense what the question is trying to do?
Recursive Snow: Yeah.
The Legendary Avenger: Awesome. So I would like to see you just resolve this and then if you can solve that, you can always extend it even further. So I have some extensions that you can always look into.
Recursive Snow: Okay, so all root to leaf numbers. So we are going to include five in there. First time I read it through, it sounded like we were just checking on the leaf numbers.
The Legendary Avenger: So like in this case, this example here will look something similar to this.
Recursive Snow: Really?
The Legendary Avenger: But it's basically right here. So two, one and three. So two to the left here. It's not necessarily a balanced binary tree here. So it's like a normal B tree.
Recursive Snow: Okay.
The Legendary Avenger: Two, one, three here.
Recursive Snow: Okay. And one thing is it sounded like the root to leaf path. So root leaf path, one, two, three represents a number 123. So is that the specific sums that we're trying or is that specific sums we're trying to do or are we doing the summing that you mentioned?
The Legendary Avenger: Yeah. So that's the specific sum that we'll be attempting to do in this regard. So in this case, so we do.
Recursive Snow: Want to move tens place around based on the leafs. Exactly. Okay. So we're going to probably do some notepad stuff here. Just a minute, I need a better angle on my keyboard. So what we're probably going to want to do is to find the values at these sort of leafs. First we're going to start at the root and we're going to keep track of track of the current sum. We're at sum is five to eight leaf. We are going to multiply the previous sum by ten to move tens place and add the leaf value. Or that might not be a leaf but go down a node. We'll just leave it as that for now. Keep doing this until we get to lead, until we get to a leaf. And then we are going to total sum of all route two leaf numbers. So if we have this tree structure right here, where we have one down here, we end up with twelve. And down here we end up with 13. Would the total that we're looking at end up being 25? So twelve plus 13 or 20, 612 plus 13 plus the one of this.
The Legendary Avenger: Actually it will be root to leaf, so it will be twelve plus 13. So this should be a 25.
Recursive Snow: Okay. So when we count the totals, we only count the value that we have once we've reached the leaf node.
The Legendary Avenger: Exactly. And in the case where let's say we have an input like this, where let's say it's only one and let's say maybe this is what thinking about. So let's say why the heck typing is coming. A bit of an issue here. So what if we had like a one and maybe just two here. So it has no left children here. What do you think that should be?
Recursive Snow: That should be twelve because since we don't have a left child, we're not going to or actually yeah, it should be twelve because two is going to be the only leaf node.
The Legendary Avenger: Exactly. So that the key bit right there is knowing what a leaf is. Right. So we are not considering anything that might have children.
Recursive Snow: Yeah, keep doing this until we get to a leaf children. Then add the sum at that leaf to the total and then just keep navigating the tree until we have all sums. Okay. So I think that covers the majority of what we want to do here. We probably want to set this up. I believe recursively is generally the way that we're going to do things for a tree. Just makes the most sense. And we're going to have to pass in the previous sum and the node we're navigating to. Okay, so I think that that's pretty good. If we wanted to write out the full thing in pseudocode, we could do that right now. Or I feel comfortable enough with this that we could move to writing it out in C sharp directly. One thing I actually do want to ask is are we going to have to write this tree structure ourselves?
The Legendary Avenger: Yes, that's actually the other bit. So yeah, we will be defining the tree structure. That's actually one of the things I wanted to see you do. But yes, feel free to do it as you please. I've seen some people using dictionaries, some people using class structure. So it's up to you.
Recursive Snow: Okay, yeah. I would probably end up using a class for this. I think I'll probably just move to the coding because what we've defined here is pretty simple and we have this sort of basic outline of this, although it doesn't have the exact architecture of what we're doing. We're going to clear out this main. This main is going to call our function. But first we want to get that tree node class. So I'm going to need to find so we're going to have our public tree node left. Public tree node, right. I do not remember if we need a constructor, but I might just put one in for 30. We are also going to want to make these nullable, lest this particular one doesn't like this annotations contextic.
The Legendary Avenger: I think we probably also need a value because it's fundamentally left right and value right.
Recursive Snow: Yes, we are also going to need a value and we're always going to value public trainer valu equals val. We can just add now it will be very simple to just make a quick simply okay. So the only thing that I have noticed is I believe the environment I usually use handles this nullable problem that we're having right now. Send nullable annotations context.
The Legendary Avenger: Maybe try three node left equals to we can initiate it as now. So instead of like making it optional, can initiate it as now.
Recursive Snow: Okay. And it doesn't have any issues with that. Okay. So I can probably remove these.
The Legendary Avenger: All right.
Recursive Snow: And then I know that that's fairly simple to go back and fix if that environment works this particular way. So we're probably going to want to do is we're going to build our input tree. Let's just do our one, two, three example for the moment. We'll just do these in line because we're only doing a couple and then we are going to why am I blanking on this? I haven't used printline in a while. It main thing, let's just get the call in place first and then not worry about something like that. Just for the moment. So our call for the moment is just going to be we're just going to call this Leaseum and we are going to give it input tree, a static int thumb root. So we're going to call into this. It just doesn't like that we don't have a value. So what we're going to do is we're going to call a different version of leaf summon here that we can call recursively a bit. Nicer. So we're just going to pass it in the root and then we are just going to pass it in an integer. Okay. So now we have the actual sort of environment that we're going to be using. This might need to be no, that should be fine. Okay. So when we get into this we're going to have a tree node. We're going to have three different possible.
The Legendary Avenger: Just my understanding in terms of naming convention. So this right here, these two functions here. So you have lift some right here which is going to be calling the function at least initiating the call here and it initiates it to the previous sum as zero right here. And then this right here basically is going to now be the generic function here and so it's going to be the one that's actually making the recursive calls, right?
Recursive Snow: Yeah.
The Legendary Avenger: Awesome. All right. Are we able to maybe rename this because it's essentially the current node not the root. It's not always going to be the root.
Recursive Snow: Right? Yeah, that's a good point.
The Legendary Avenger: Same case with the function.
Recursive Snow: Sorry I didn't hear that.
The Legendary Avenger: Yeah, I think you might also want to rename the function. That way at least we know what it's doing. Right?
Recursive Snow: Sure. Cursive and then I believe because this is C sharp it wants us to capitalize. Wait. Oh no, it's just complaining about code paths. Okay. So we're going to have three different possible situations that we run into when we get here. What we really want to check first is if our is if these are both null. And then this is going to be our base case where we've reached a leaf and we can sort of return our previous sum. We're going to return our current sum which will calculate up here. Current sum will just be I referred to this as total earlier. So we will change that to total. So current total is just going to be previous total intensity and we are going to add current value to it. Okay. So if we don't have either of these, we're just going to return our current total and then see. Okay. Yeah, that's completely fine for there. And then we handle the other stuff when we get down to here. So we have at least something that isn't null. So if current left is not equal to null, that means we have a current left that we can work with. So we are going to do we're going to make a result here and initialize it to zero. So if we have a left, we're going to do results plus equals a leaf sum recursive on current left. And then our prev total is going to be our current total in here. Then we just do the same thing for the right path.
The Legendary Avenger: Just for my understanding. Again, in this case, we're checking if we've hit the leaf and then if we ever hit the leaf, we return the current total. And then for these two, what we are doing is we're essentially calculating down. Actually it's not calculating, it's actually going down the tree to find the lease, right?
Recursive Snow: Yeah, we're going down the tree to find the lease.
The Legendary Avenger: I see.
Recursive Snow: Yeah. Go ahead. Sorry.
The Legendary Avenger: So the way I'm thinking of it here is you have the values that you're exploring. So at any given point, you have a node. You have a current node, right?
Recursive Snow: Yeah.
The Legendary Avenger: And so that node has a value and you want to be attaching that value like building it up from the top. Because what you saw was if we have, let's say the one to three example, we are coming from the top, we have one and then we have the two. If we add any more, we basically are attaching them. So it's kind of building itself as we go. And then as soon as we hit the leaf, we have a value and that's what we add. Yeah, right. And so what will the result really do for us here? Like this result right here?
Recursive Snow: So this result is basically that's our way of passing up the so each time we reach a leaf, we get one of the numbers that we're going to add into the result that we finally get from the entire function. What this result does is if we have both a left node and a right node. We're going to need to get the numbers from both of them together.
The Legendary Avenger: I see.
Recursive Snow: And then pass that back up the tree. Yeah.
The Legendary Avenger: Excellent. Okay, that makes sense.
Recursive Snow: Okay, so once we get those, that should be enough to just return the result as is that will keep traveling back up the tree. I believe that should be all that we need to do to get a basic run. Except that we want to do a quick print for this. Yeah. So that was just console that and let's see what we get running this the first time. Okay, so we have the nulls that we just need to change. So that is what I see. Okay. Yeah, we just need to change that for semantics. Okay, so it looks like this works. So what we probably want to do now is to start running some tests just to make sure that things work properly. Let's make sure these should be very simple but just doing quick check to make sure that it will handle these properly. Node three. Okay, so those seem to be fine. We're just going to leave this one here and let's make an input tree B. So now we should probably test some more complicated cases. Actually one really obvious case that we should definitely test is what happens if we just pass in the root whoops. I need to rename this and that looks like it works fine. Okay, so let's do something a bit more complex. What is a good thing to test for this? We should probably test a tree that has leaf nodes that aren't all on the same level. So I'm just going to do.
The Legendary Avenger: We'll.
Recursive Snow: Just make a quick text representation up here of some of the trees that we'll be testing.
The Legendary Avenger: Actually you can just write them out without the slashes. I know they throw people off in that case. Yeah, I've noticed they are really hard to work with.
Recursive Snow: Okay. So we should probably have something more along the lines of this where's we should probably also have something more along the lines of this just to have and we'll just put nulls. Well, those will just be empty so that we have different so if roots on different levels, we can just work this out really quickly. So 124 plus 125 is going to be 249 plus 13 is going to be that's 262. Yeah, we will do a quick separator above these just to put in the value that we're expecting. Okay, so let's build this tree. So we're going to do new tree node. We're just going to put in a null for now and then new tree node three, we are going to do tree node input tree BL going to be the left side of this tree that we're just going to put here. So we don't have a really long line. Okay. So that should be correct. We just need to do input tree left equals input tree BL. Okay. So let's run this and see how it runs. We got 262. Okay, so that looks like it runs good. The only thing that I will change for the moment is we'll have the same output. We're just going to put this on the right side just to make certain that it handles it on the right, although I don't see any reason why it would not.
The Legendary Avenger: All right.
Recursive Snow: Okay, I think that this seems pretty good. I can't think particularly of any other cases that we'd want to test for other than it's mentioned up here that the inputs that we get should all fit into a 32 bit integer and that's just as a matter of test cases. And that would basically be the only thing that I would think of for testing at the moment.
The Legendary Avenger: This should be good. Yeah, I think this really works well. And I was actually just laughing at myself looking at the output, even. It says your name, recursive Snow. That's your alias. Clearly he got the recursion band right here. So really good luck right there. So maybe talk to me about the complexity for this is both time and space.
Recursive Snow: Okay, so complexity I need to think on for a minute. Complexity for recursive stuff is something I do not have directly on the mind. When it comes to space complexity, though, this is pretty lightweight. We basically just have our input tree and then all we're really doing is we're just using a handful of integers to tally our results. So it's basically we're going to have an input complexity of the complexity of one for extra space since our input tree is not going to be counted. And then when it comes to the time complexity, that's probably just going to be I think that should end up essentially working out to O of N because we are going to be just visiting every single node in the data once we don't have to revisit anything. It's just going to work out to be yeah, trees grow in a bit of a weird way, but when we're considering the raw number of nodes that are going to be in it, it's just going to be O of N for runtime. All right, I believe.
The Legendary Avenger: Yeah, that sounds about right here. Because Japan, we kind of have to explore all the paths, really from the root to pretty much all the lists, so it's actually over. So that's good. And yeah, you're right. The way you implemented it is what really works well here. Like we're tracking the sum as you compute, so it's actually going to be just single memory for each recursive call. So it's all one. So that's good. Okay, so this is good. Analysis is spot on, every implementation is spot on. So let's actually tackle the had a variant of this question. So what if instead of the total sum, we were interested in the maximum path sum. And by that what I mean is if say you look at, let's say, the third example, this one right here on line 63 to 65. So the maximum path sum for us would be from five to two to one to three. So that's kind of like left to right path sum here. So how would you compute that? So that's kind of the next step with this.
Recursive Snow: Okay, so what we're probably going to want to do is there are things that we could look at with this. Such as? Basically because we don't know the exact structure of the tree. We know that we can't really throw anything out too early, unfortunately, because if we knew that all of our nodes down here were going to be populated, like we knew 100% that we had a six and a seven here, when we're at this one, we'd have two or three next. We could cut down on time. We could cut down on quite a lot of time because if we knew that all of our leafs are on the same level that exploring the two path is pretty pointless because everything on the three path would be larger. But we can't make that optimization because we don't know or not all of our leases are on the same level.
The Legendary Avenger: I'll note the one bit here and this is actually the intent, we're not calling it a BST. It's not a binary search tree because you can see we have a five here which is smaller than a value on the right side. So it's really not about that. We cannot make that assumption that anything on the right is always going to be larger. Right?
Recursive Snow: We can with this particular set up though because if we know that, because everything, we have one here and then we get to twelve and then everything down here is going to be 120 something but we would know that everything on this side is going to be 130 something. So we know for sure that this side would be larger. It's just a matter of we can't make that particular optimization because we might not have all leafs on the same level.
The Legendary Avenger: Sorry, I was clarifying. Okay, let's actually maybe don't understand that fully here but okay, so if we are at so we know it's 130 something, right?
Recursive Snow: Yeah.
The Legendary Avenger: In this case it's possible that we could have 137 and this is the one that's 136. Like they can be flipped based off of our setup. It's not a BST, it's a binary tree. So just two way in this case. And so it's possible that the left child here can be larger than the right child.
Recursive Snow: Yeah. It's possible that this because what we're talking about when it comes to the sums, because the actual sums that we're looking at to find the best lease node involve everything that's further up the tree as well, because this node represents 137, not just seven.
The Legendary Avenger: Indeed.
Recursive Snow: Yeah. Which is why, because when we get to here, we do have to check both of these just to make sure. And we're at the leaf level, so we know that whatever we have down here is sort of our final answer. But when we're up here, we do know that all of the leaf nodes down here, because of this previous tens place exists, are going to be larger than these ones because of this previous tens place.
The Legendary Avenger: Because I see what you're saying. Okay.
Recursive Snow: Yeah.
The Legendary Avenger: All right, that makes sense.
Recursive Snow: Yeah. But that is one optimization we can't make because if we had a tree like this, we would just throw out the other side and we would end up with an answer that's only 13, which is very much not correct.
The Legendary Avenger: Exactly.
Recursive Snow: Yeah. So what we're probably going to want to do is since all we need to do is find the maximum, we don't want to use much extra space and then have to sort of navigate the extra space that we do have. What we probably want to do is the easiest way would be to have some sort of class member. I think ideally we would have a separate class for everything that calculates our leaf sum and everything. But for convenience sake, we're just going to set up out here in solution, a sort of class member variable that we'll just use to calculate current max. And we will initialize this to zero so we can access current max from basically wherever. So now that we have our new goal, basically we can modify some of this just to we'd probably not want to return these. I'll just leave them in here. We're doing a bit of extra work, but we don't really need to worry about them. So we're going to add another right line that will get the value of the maximum path. Actually, that is an important question. Do we want the value of the maximum path?
The Legendary Avenger: Yes. Are we interested in the sum of the maximum path in this case? It's kind of different to what we've been calculating in this case. So it's not going to be 125 plus, let's say 13, it's going to be the five plus two plus one plus three. Right. So we actually want the individual values in this case, but I think they're kind of related because honestly, if we have 124, let's say that's actually a good question because 129 might be bigger than 125.
Recursive Snow: Actually.
The Legendary Avenger: No, I meant 129 in this case. I'm actually evaluating if we had, let's say, an objectively bigger value. Like, is it some strictly bigger? Because when I think of it. 129 might be smaller. I might be bigger than, let's say 131, but at the same time, they have a shared core there, so that's not really a possibility. So that kind of is fine, but it will be up to you. That's all my thought process at the moment.
Recursive Snow: Okay. Yeah. What I think that we're going to do is we have this current max that's just going to keep track of the sort of maximum value that we found at a leaf node. And all we really need to change here is when we get down to here where we have okay. So all we really want to do is just check if current total is greater than our current max. Then we are just going to change current max to be current total.
The Legendary Avenger: That's good. So you're using a global variable in this case that can be modified by any of the recursive calls, right?
Recursive Snow: Yeah. Just because that's going to be the easiest it's going to be the easiest way or the least modification we'd have to do for the code. If we didn't want to use that, it would be possible to sort of be possible to pass this stuff around, although it's not really that convenient. We'd have to change quite a few things. But if this is within sort of the realm of what we want to do, keep track of things with the class variable, then that's probably the best way to do it. We should also run this just to make sure it's working properly.
The Legendary Avenger: Keep in mind the bit that I printed out on, we want the sum of the individual values, not the sum of the part itself. So that's the only thing to be mindful of here.
Recursive Snow: Okay. So when we're comparing this part, we're adding one plus two plus four.
The Legendary Avenger: Exactly. Yeah. So it's one plus two plus four, one plus two plus five.
Recursive Snow: Okay.
The Legendary Avenger: Yeah. And that's kind of why I went on that tangent, wondering, okay, let's say 130 bigger than 129 or something. That's kind of why I was asking myself that.
Recursive Snow: Okay. Yeah. Okay. So that's a bit different. So first off, we're going to need to modify this to also keep track of a max total as we're moving through these. No, I do. Not. So our max total will just keep track of the individual numbers. We don't multiply them by ten. So max total is just going to be max total plus current value. Okay. And now first thing we're going to do is current max total. Change these the right numbers and those are good. We need to fix these calls down here to use current max total as well. And I think those are the primary changes that we would need. That should carry through everything properly. Let's run it to double check. Or actually, let's also just do a quick add something up here to give it the output that we should end up with. This should end up with four, this should end up with 5678. Okay, so that works out. We should probably add a new test case just to double check. Let's just do something like this, 121245. And then over here we have nine. This we should get 124. It's basically just the above plus six. So it would be 200 plus six. Yeah, that's correct. So that would just be 268. And then ten should be our other value. So let's make this tree down here. This will be our tree. We can just copy all of this. Actually, we just need to change this to nine. That should all be right, let's run this. That should be 268 and ten. Something happened. Let me make sure that's not just me, that's just me putting something wrong in the tree. Okay, yeah, I forgot I reversed the left and right on this tree when I copied it over. That should be yes, that works excellent. Okay, so, yeah, I think that covers what has been asked for.