• Post Reply Bookmark Topic Watch Topic
  • New Topic

Java tree structure exercise, build the tree based on travseral results  RSS feed

 
Caroline walkers
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi all,

Can you help to explain the logic of how to do draw the original binary tree based on traversal results? Many thanks in advance!

A binary tree has this pre-order traversal result: A,B,D,H,I,E,F,C,G,K,J (TreeNodes) And the same tree gives the following in-order traversal: B,H,I,D,A,C,F,E,K,G,J. Can you draw the tree structure?
 
Stevens Miller
Bartender
Posts: 1445
30
C++ Java Netbeans IDE Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That's not really a Java question, but it's a good puzzle. Let me make two suggestions: First, read the Wikipedia page on this topic. It's pretty good and has some helpful diagrams. Second, draw yourself some very simple binary trees, maybe starting with only two nodes, then three, then four, and write out the result of each type of traversal on them. As you do that, you may see patterns that apply to larger trees.

For example, the simplest tree has one node, A, and its traversal results for pre-order and in-order are A and A. A tree with two nodes can be structured one of two ways:


or


The first tree's pre-order and in-order traversals are AB and BA. The second tree's traversals are AB and AB. Hmmm... already we see a difference. How many trees with three nodes are there?


Each has these traversals


ABC, CBA
ABC, BCA
ABC, BAC
ABC, ACB
ABC, ABC

(Check me on the in-order traversals above; been a long time since I did this.)

Do you see relationships appearing between the structure of the trees, and how the nodes appear in each traversal? Maybe you can figure out a rule that will let you break the traversals into sub-traversals, applying that rule repeatedly until you break a traversal down to just one node, then work your way back up from there.

That's not a direct answer, but that's kind of how it works here.
 
Campbell Ritchie
Marshal
Posts: 56584
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And welcome to the Ranch

If you have parse trees, which you can find on articles similar to what you have been given, you find that a postorder traversal gives you the expression back in postfix, and simlarly for the other two kinds of depth‑first XYZorder traversals.
 
Caroline walkers
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks guys! I am new to Java..and will google what a parse tree is (:
 
Stevens Miller
Bartender
Posts: 1445
30
C++ Java Netbeans IDE Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Good luck. Don't worry about being new to Java. The problem you are working on is an abstract question about a data structure. It doesn't involve Java at all.

Now, writing a Java program to accept those two traversal results you've got and reconstruct the original tree from them... ah, that would be something to worry about.

But, if you need us, we'll be here.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!