Binary Search Tree - Postorder logic

Posted by daveb on Stack Overflow See other posts from Stack Overflow or by daveb
Published on 2012-03-13T16:44:42Z Indexed on 2012/03/22 17:29 UTC
Read the original article Hit count: 313

Filed under:

logic

|

binary-trees

|

binary-search

I am looking at implementing code to work out binary search tree. Before I do this I was wanting to verify my input data in postorder and preorder.

I am having trouble working out what the following numbers would be in postorder and preorder I have the following numbers 4, 3, 14 ,8 ,1, 15, 9, 5, 13, 10, 2, 7, 6, 12, 11, that I am intending to put into an empty binary tree in that order.

The order I arrived at for the numbers in POSTORDER is

2, 1, 6, 3, 7, 11, 12, 10, 9, 8, 13, 15, 14, 4. Have I got this right?

I was wondering if anyone here would be able to kindly verify if the postorder sequence I came up with is indeed the correct sequence for my input i.e doing left subtree, right subtree and then root.

The order I got for pre order (Visit root, do left subtree, do right subtree) is 4, 3, 1, 2, 5, 6, 14 , 8, 7, 9, 10, 12, 11, 15, 13. I can't be certain I got this right. Very grateful for any verification.

Many Thanks

© Stack Overflow or respective owner

Related posts about logic

Business Logic Layer Pattern on Rails? MVCL

as seen on Stack Overflow - Search for 'Stack Overflow'
That is a broad question, and I appreciate no short/dumb asnwers like: "Oh that is the model job, this quest is retarded (period)" PROBLEM Where I work at people created a system over 2 years for managing the manufacture process over demand in the most simplified still broad as possible, involving… >>> More
What is the correct way to deal with similar but independent features?

as seen on Programmers - Search for 'Programmers'
Let's say we have a feature request come in and we begin work on it, which we'll call feature-1. It introduces some new logic to the application, which we'll call logic-A and logic-B. A programmer branches from the release branch and begins work on the feature. Soon after, we get another feature… >>> More
What is up with the Joy of Clojure 2nd edition?

as seen on Programmers - Search for 'Programmers'
Manning just released the second edition of the beloved Joy of Clojure book, and while I share that love I get the feeling that many of the examples are already outdated. In particular, in the chapter on optimization the recommended type-hinting seems not to be allowed by the compiler. I don't know… >>> More
Transforming Business Logic into Web Services Using DB2 9.5 and IBM Data Studio

as seen on Internet.com - Search for 'Internet.com'
Learn how to take business logic such as stored procedures, functions, or SQL statements and turn them into a Web service. >>> More
Identifier for the “completed” stage of a process: 0, 99, something else?

as seen on Programmers - Search for 'Programmers'
Say, that you are handling a multi-step process (like a complex registration form, with a number of steps the user has go through in order). You need to be able to save the current state of the process (e.g. so the user can come back to that registration form later and continue form the step where… >>> More

Related posts about binary-trees

Binary Trees in Scheme

as seen on Stack Overflow - Search for 'Stack Overflow'
Consider the following BNF defining trees of numbers. Notice that a tree can either be a leaf, a node-1 with one subtrees, or a node-2 with two subtrees. tree ::= (’leaf number) | (’node-1 tree) | (’node-2 tree tree) a. Write a template for recursive procedures on these trees. b. Define the procedure… >>> More
C++ design question on traversing binary trees

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a binary tree T which I would like to copy to another tree. Suppose I have a visit method that gets evaluated at every node: struct visit { virtual void operator() (node* n)=0; }; and I have a visitor algorithm void visitor(node* t, visit& v) { //do a preorder traversal using… >>> More
Priority queues and Binary trees

as seen on Stack Overflow - Search for 'Stack Overflow'
Trying to create a game using priority queues and binary tree, for example a solitaire game. I hope this is not to vague? >>> More
What are the applications of binary trees?

as seen on Stack Overflow - Search for 'Stack Overflow'
I am wondering what the particular applications of binary trees are. Could you give some real examples? Thanks. >>> More
A deque based on binary trees

as seen on Programmers - Search for 'Programmers'
This is a simple immutable deque based on binary trees. What do you think about it? Does this kind of data structure, or possibly an improvement thereof, seem useful? How could I improve it, preferably without getting rid of its strengths? (Not in the sense of more operations, in the sense of different… >>> More