2
$\begingroup$

The question is: given a sequence of numbers, find an algorithm that determines if the sequence of numbers is in post order traversal of a binary search trees.

Up to now, I have understood the following:

  • In the post order traversal of the binary tree it follows Left, Right, Root. So the Left value has to be less than the Right value.
  • The last element of the sequence is the root, assuming the sequence was in the post order traversal.

I do not know how to progress further with this. Also, is there a way to create a Divide and Conquer algorithm for this?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Don't fixate on a particular style of algorithm. Try to figure out what would be appropriate to the task you're trying to perform. $\endgroup$
    – David Richerby
    Commented Mar 30, 2017 at 7:41
  • $\begingroup$ Come and talk to me in my office hours if you have questions. Don't try cheating by asking for the answers online. $\endgroup$
    – Jacquelin Smith
    Commented Apr 1, 2017 at 18:47
  • $\begingroup$ The problem statement appears to be copied, word-of-word, from University of Toronto's CSC236 Assignment #3, due April 5th. Please make sure to provide proper attribution for your sources. $\endgroup$
    – D.W. ♦
    Commented Apr 1, 2017 at 21:13
  • $\begingroup$ Separately: If you are a member of the course, I recommend you consult the course academic integrity policy to confirm what kinds of uses of external sources are appropriate. If you are not a member of the class, it might be better to avoid posting questions about the homework until after the due date. You might find this page helpful in asking questions based on homework. $\endgroup$
    – D.W. ♦
    Commented Apr 1, 2017 at 21:14

1 Answer 1

Reset to default
3
$\begingroup$

Probably you consider binary search trees, otherwise the exercise is a little useless.

You already concluded that your input has postorder: post-left-subtree, post-right-subtree, root. Now the value of the root determines which values belong left, and which values belong right. So you are right: this is divide and conquer. Split the numbers according to the subtrees, and repeat for each of the two subtrees.

If a split of the input does not have the form post-left-subtree < root < post-right-subtree, you know what to conclude from that.

An example. The sequence is 1, 5, 9, 7, 3, 13, 17, 15, 11. So the root is 11. And we can split the sequence accordingly into left and right subtrees: 1, 5, 9, 7, 3 < 11 < 13, 17, 15. Continue with the left and right subsequences.

Another sequence is 1, 5, 13, 9, 7, 3, 17, 15, 11. No split 'at' 11 possible.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I need to conclude that my input has post order. I just listed the things I know about a post order traversal. I'm unable to translate that properly into an algorithm. I feel like I'm overthinking this problem. $\endgroup$
    – R83nLK82
    Commented Mar 30, 2017 at 4:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.