• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Bear Bibeault
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Paul Clapham
  • Devaka Cooray
  • Knute Snortum
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Frits Walraven
Bartenders:
  • Carey Brown
  • salvin francis
  • Claude Moore

Reconstruction of a binary search tree with preorder traversal and divide and-conquer-principle  RSS feed

 
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I know this isn't really a Java based question but i didn't know where to post it else.
Given is the preorder traversal 5, 3, 1, 2, 4, 8, 7, 6, 9 of a binary search tree. I now whant to reconstruct the tree with the divide and-conquer-principle.
I do understand the preorder traversal but isn't it necessary to know the preorder as well as the inorder traversal to reconstruct the tree?
If anyone has an idea how to solve this, please give me a hint because I'm kind of lost here.
 
Saloon Keeper
Posts: 10136
214
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to CodeRanch!

Why would you need to know the inorder traversal? The preorder traversal is a complete description of the tree. As long as the number is less than the previous, you add it as the left child of the previous node. If it's greater, you go back up the tree and add it as the right child of the first ancestor that is greater. There is a really easy way to do this: Create a root node out of the first number, and then repeatedly add the other numbers to the root. If the number is less, then recursively add it to the left sub-tree. If the number is greater, then recursively add it to the right sub-tree. When a sub-tree is null, you have found the final location of the number.

If you only had the inorder traversal, you wouldn't have enough information to recreate the tree. The inorder traversal always yields 1, 2, 3, 4, 5, 6, 7, 8, 9, regardless of the structure of the tree.
 
Ranch Hand
Posts: 380
2
Fedora IntelliJ IDE Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:There is a really easy way to do this:


Can you also explain an easy way to do the same for in-order and post order, please?
 
Stephan van Hulst
Saloon Keeper
Posts: 10136
214
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For post-order, you just reverse the sequence and then perform the same algorithm.

Stephan van Hulst wrote:If you only had the inorder traversal, you wouldn't have enough information to recreate the tree.



[edit]

I apologize. Reversing the sequence would of course not be valid for the  post-order traversal. The post-order traversal for the tree recreated from the sequence given by the OP would be:

2, 1, 4, 3, 6, 7, 9, 8, 5.

Let me quickly think of an easy way to construct this tree.
 
Stephan van Hulst
Saloon Keeper
Posts: 10136
214
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay, here's an easy algorithm you can use for both pre-order and post-order, which can also be performed concurrently for left and right sub-trees, which is likely what Hans means by a divide-and-conquer algorithm:

First remove the first or last element from the input sequence, depending on whether it is a pre- or post-order traversal. This element is the root of the current tree. Then split the remaining sequence into a sub-sequence that is smaller than the root, and a sub-sequence that is larger than the root. Then recursively create sub-trees for these sub-sequences. If you like you can process the recursive sub-sequences in parallel.
 
Master Rancher
Posts: 3189
119
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Given the postorder sequence 2, 1, 4, 3, 6, 7, 9, 8, 5

it seems like what you proposed (reverse the list and build the BST from that reversed sequence) works. What is then wrong with it?
 
Stephan van Hulst
Saloon Keeper
Posts: 10136
214
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, somewhere down the line I convinced myself that algorithm wouldn't work for ALL postfix sequences, but I was mistaken.

However, the algorithm I described in my previous post fits the "divide-and-conquer" requirement of the original problem description.
 
Hans Peterson
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm not quite sure if I understand your algorithm right.
First I define 5 as my root, so I have the elements 3,1,2,4 which are smaller than five and therefore are on the leftside and the elements 8,7,6,9 which are greater than 5 and therefor are on the rightside.
In the next step I compaare 1,2 and 5 to 3. Is this right?
So 1 comes to the left side of the subtree and 3 to the rightside. In the end, 2 is greater than 1 and therefore stands on the rightside.
The same way are the elements on the right side placed.
Did I execute your algorithm right?
 
Stephan van Hulst
Saloon Keeper
Posts: 10136
214
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, exactly.
 
Piet Souris
Master Rancher
Posts: 3189
119
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
But assuming you have a BST class with Nodes, then you already have all this logic built-in. Why re-invent the wheel?
 
this is supposed to be a surprise, but it smells like a tiny ad:
Create Edit Print & Convert PDF Using Free API with Java
https://coderanch.com/wiki/703735/Create-Convert-PDF-Free-Spire
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!