What are the in-order and post-order traversals of the following tree?
-
With respect to [this tree](https://i.stack.imgur.com/wh8Et.jpg), 1. What is the correct in-order traversal? 1. U S T X C P Y R B A I G J F N H V T E D L 2. U S T X C P Y R B A D E I G J F N H V T L 2. What is the correct post-order traversal? 1. U T S X P R Y C B D I J G N V T H F E L A 2. U T S X P R Y C B I J G N V T H F E D L A I evaluated both pairs. But some are saying 1-1 and 2-1 are correct, while others say 1-2 and 2-2 are correct. I'm confused. Which ones are actually correct?
-
With respect to [this tree](https://i.stack.imgur.com/wh8Et.jpg), 1. What is the correct in-order traversal? 1. U S T X C P Y R B A I G J F N H V T E D L 2. U S T X C P Y R B A D E I G J F N H V T L 2. What is the correct post-order traversal? 1. U T S X P R Y C B D I J G N V T H F E L A 2. U T S X P R Y C B I J G N V T H F E D L A I evaluated both pairs. But some are saying 1-1 and 2-1 are correct, while others say 1-2 and 2-2 are correct. I'm confused. Which ones are actually correct?
1-2 and 2-2, maybe. I'll explain the reasoning, and why there is a "maybe". Let's do the post-order one first, that's easier. OK so both answer start with "U T S X P R Y C B", so let's say we've just gone up out of B, and are looking at A right now (not "visiting" it yet though), so we recurse into L, which recurses into D, into E, into F, into G, into I, and then we come back up, so after B comes I, not D. Or to put it in a different way: in a post-order traversal, a node is visited only after all its descendants, so there is no way D could be in the middle of this sequence, it has to be near the end. Only L and A could ever go after it. The in-order question has two answers that start with "U S T X C P Y R B A", so let's say we're at A again, recursing into L, D, D's left child (null), then D itself, so it's the second answer. But here's why I added "maybe": "U S T X C P Y R B A" is not even the right sequence to start with, because it puts B after C but C is the right child of B so B should been visited before C. Both answers are wrong. But the first answer is worse: it gets more of the sequence wrong.
-
1-2 and 2-2, maybe. I'll explain the reasoning, and why there is a "maybe". Let's do the post-order one first, that's easier. OK so both answer start with "U T S X P R Y C B", so let's say we've just gone up out of B, and are looking at A right now (not "visiting" it yet though), so we recurse into L, which recurses into D, into E, into F, into G, into I, and then we come back up, so after B comes I, not D. Or to put it in a different way: in a post-order traversal, a node is visited only after all its descendants, so there is no way D could be in the middle of this sequence, it has to be near the end. Only L and A could ever go after it. The in-order question has two answers that start with "U S T X C P Y R B A", so let's say we're at A again, recursing into L, D, D's left child (null), then D itself, so it's the second answer. But here's why I added "maybe": "U S T X C P Y R B A" is not even the right sequence to start with, because it puts B after C but C is the right child of B so B should been visited before C. Both answers are wrong. But the first answer is worse: it gets more of the sequence wrong.
Thanks for your reply. Below is my takeaway from your post. Post-order traversal > Or to put it in a different way: in a post-order traversal, a node is visited only after all its descendants Your statement quoted above was enough to clarify me about the post-order traversal. I believe, that makes the following series as the correct answer: U T S X P R Y C B I J G N V T H F E D L A In-order traversal According to your explanation, while traversal, if any node has a null left child, that node has to be visited right away as the immediate root node before moving down further. If I'm right, then, I think the following series is the correct answer: B U S T X C P Y R A D E I G J F N H V T L
-
Thanks for your reply. Below is my takeaway from your post. Post-order traversal > Or to put it in a different way: in a post-order traversal, a node is visited only after all its descendants Your statement quoted above was enough to clarify me about the post-order traversal. I believe, that makes the following series as the correct answer: U T S X P R Y C B I J G N V T H F E D L A In-order traversal According to your explanation, while traversal, if any node has a null left child, that node has to be visited right away as the immediate root node before moving down further. If I'm right, then, I think the following series is the correct answer: B U S T X C P Y R A D E I G J F N H V T L
