Author |
Topic: Traversing a Binary Tree (Read 2492 times) |
|
Dudidu
Full Member
Posts: 227
|
 |
Traversing a Binary Tree
« on: Dec 4th, 2003, 7:26am » |
 Quote  Modify
|
You are given a binary tree...
(1) Given a preorder walk and postorder walk of the tree, is reconstruction of the tree possible ? (and if it is, devise an algorithm that will do it)
(2) Given a preorder walk and in-order walk of the tree, is reconstruction of the tree possible ? (and if it is, devise an algorithm that will do it)
(3) Given a preorder walk of a binary search tree, is reconstruction of the tree possible ? (and if it is, devise an algorithm that will do it)
For more information see preorder traversal, in-order traversal and postorder traversal.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Traversing a Binary Tree
« Reply #1 on: Dec 4th, 2003, 8:02am » |
Quote Modify
|
Just to be clear, can I assume there are no nodes that have both a non-empty and an empty subtree? Or otherwise that order isn't important in those cases..
One other thing, can I assume all values in the nodes are different (when they're all the same it's also rather problematic)
|
| « Last Edit: Dec 4th, 2003, 8:28am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Traversing a Binary Tree
« Reply #2 on: Dec 4th, 2003, 8:38am » |
Quote Modify
|
1> i don't think it can be done (atleast cannot be done in an efficiently without exhaustive analysis of all possible trees)
2>this is possible , i have not come up with any general algo for it yet.
3>thinking!
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Traversing a Binary Tree
« Reply #3 on: Dec 4th, 2003, 8:52am » |
Quote Modify
|
I've got one question and one comment:
Q. Can we assume that with every node of the tree is associated a unique number 1..N (without any particular order), and that the representations given are just the permutations of (1 2 ... N)? (I guess towr asked similar question).
C. If the answer to 3) is yes, doesn't it mean the answers to 1) and 2) are also yes?
Certaintly, I'm missing something...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Traversing a Binary Tree
« Reply #4 on: Dec 4th, 2003, 8:56am » |
Quote Modify
|
In 3 you probably missed 'binary search tree', I did as well the first time..
Either way it's a tripple yes.. (under my previous assumptions)
also, 1) can be done in O(n) (using a hashmap which is O(1), and otherwise O(n log(n)) is still easy enough)
and the others probably as well..
|
| « Last Edit: Dec 4th, 2003, 11:09am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Traversing a Binary Tree
« Reply #5 on: Dec 4th, 2003, 1:02pm » |
Quote Modify
|
here's a bit of MOO-code for 3)
I suppose it's not as clean as it might be, but it works..
::
{a, m} = args;
if (a && ({h,@b} = a) && (h < m))
{left,b} = this:verb(b,h);
{right,b} = this:verb(b,m);
if(left || right)
return { {h,left,right}, b};
else
return {h, b};
endif
else
return {{},a};
endif
[e] example call:
;player:verb({2,1,4,3,5},max({2,1,4,3,5})+1)[1]
So the input arguments are a preorder, and some value greater than the maximum (to start off with)
This call returns {2,1,{4,3,5}} [/e]
::
|
| « Last Edit: Dec 4th, 2003, 2:30pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
towr, look at the attached figure. If I am not mistaking, all your assumptions are met. But both trees have the same preorder sequence.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Traversing a Binary Tree
« Reply #7 on: Dec 5th, 2003, 12:10am » |
Quote Modify
|
Those aren't binary search trees though..
A binary search tree is characterized by every node in the left subtree being smaller than the root, and every node in the right subtree being greater then the root.
So unless you can make it so they are also both binary search trees, or have the same postorder or inorder, it doesn't matter.
The easiest way to see how 3) can work is to realize that you're essentially just building the search tree with the values as they come in. The root node comes first, then the root of the left subtree, then the root of the left subtrees left subtree etc
Because it's a binary search tree you allways know where the next value has to go in the tree. The root of the left subtree has to be smaller than the node itself. If the next value in the preorder isn't smaller, then it can't be in the left subtree. If the next value is greater than the current node, and smaller than the parent node, then it can only be in the right subtree.
And doing it efficiently you can do it in O(n), rather than O(n2) worst case (O(n log(n) ) average) for building a BST from a random set of values.
|
| « Last Edit: Dec 5th, 2003, 12:18am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Traversing a Binary Tree
« Reply #8 on: Dec 5th, 2003, 6:29am » |
Quote Modify
|
Ok, now I see... Not only I missed the word 'search' in the original Dudidu's posting, but also didn't put enough attention to your previous post...
I am too unfocused... 
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Traversing a Binary Tree
« Reply #9 on: Dec 5th, 2003, 11:58pm » |
Quote Modify
|
Note that a binary tree is a search tree iff its in-order traversal is strictly increasing, so that (2) implies (3).
Conversely, given an in-order traversal, we may use that as the definition of the order, making it a search tree; then (3) implies (2).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Traversing a Binary Tree
« Reply #10 on: Dec 6th, 2003, 5:53am » |
Quote Modify
|
But extracting that order between any two elements from the inorder notation isn't trivial, so it would be harder to keep the algorithm O(n)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Traversing a Binary Tree
« Reply #11 on: Dec 7th, 2003, 4:53am » |
Quote Modify
|
Everybody hi,
Sorry that I couldn't reply sooner:
Quote:can I assume there are no nodes that have both a non-empty and an empty subtree? Or otherwise that order isn't important in those cases..
|
|
NO (for both questions) !
Quote:| can I assume all values in the nodes are different (when they're all the same it's also rather problematic) |
|
Quote:| Can we assume that with every node of the tree is associated a unique number 1..N... |
|
YES.
Quote:| here's a bit of MOO-code for 3) |
|
towr, I don't understand the code (sorry)  . Does this code is still relevant after my previous answers ?
Quote:| Note that a binary tree is a search tree iff its in-order traversal is strictly increasing, so that (2) implies (3)... |
|
Eigenray, well done  . This distinction is very important (since it explicitly indicates that the 2nd sub-question is harder then the 3rd sub-question).
I know that some of the previous answers will change now due to the "collapse" of some assumptions. So... waiting for your answers  .
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Traversing a Binary Tree
« Reply #12 on: Dec 7th, 2003, 7:21am » |
Quote Modify
|
on Dec 7th, 2003, 4:53am, Dudidu wrote:| towr, I don't understand the code (sorry) . Does this code is still relevant after my previous answers ? |
|
Yep, it works just fine..
As for how it works, starting with the list {2,1,4,3,5}:
//call with: {2,1,4,3,5}, 6
{a, m} = args;
// a = {2,1,4,3,5}, m = 6
if (a && ({h,@b} = a) && (h < m))
// a is non-empty, h=2, b = {1,4,3,5}, 2 < 6: we're in the correct subtree, if h > m this subtree would be empty
{left,b} = this:verb(b,h);
// left=1, b = {4,3,5}
{right,b} = this:verb(b,m);
// right={4,3,5} , b = {}
if(left || right)
return { {h,left,right}, b};
// return_value: subtree={2,1,{4,3,5}} , leftover_list = {}
else
return {h, b};
endif
else
return {{},a};
endif
The first question won't (allways) have a solution though, not without each node having either two, or no subtrees.
1 1
/ \ and / \
nil 2 2 nil
are both {1,2} in preorder and {2,1} in postorder, for instance, so there is no way to distinguish, and thus no way to reconstruct..
Which is a shame, since with my assumption I'm positive it can be done.
|
| « Last Edit: Dec 7th, 2003, 7:25am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Traversing a Binary Tree
« Reply #13 on: Dec 7th, 2003, 7:42am » |
Quote Modify
|
on Dec 7th, 2003, 7:21am, towr wrote:| Yep, it works just fine... |
|
towr hi,
I've re-looked at your code and it seems to be correct (although I'm not sure, since I haven't looked into it deeply enough).
Quote:| The first question won't (allways) have a solution though, not without each node having either two, or no subtrees. |
|
Again, you're right !
Quote:| Which is a shame, since with my assumption I'm positive it can be done. |
|
Shame or not shame, this is the question (sorry)...
Still, sub-question (2) hasn't been solved...
|
| « Last Edit: Dec 7th, 2003, 7:44am by Dudidu » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Traversing a Binary Tree
« Reply #14 on: Dec 7th, 2003, 8:29am » |
Quote Modify
|
on Dec 7th, 2003, 7:42am, Dudidu wrote:| Still, sub-question (2) hasn't been solved... |
|
Well, no solution had been posted..
But here's one..
MOO again, but I'm sure if you try you'll understand it (eventually) 
::
{preorder, inorder} = args;
l=length(preorder);
if (l > 2)
i = preorder[1] in inorder;
return {preorder[1],
this:verb31(preorder[2..i], inorder[1..i-1]),
this:verb31(preorder[i+1..$], inorder[i+1..$])};
elseif (l == 1)
return preorder[1];
elseif (l == 2)
return preorder==inorder ? {preorder[1], {}, preorder[2]} | {preorder[1], preorder[2], {}};
else
return {};
endif
::
This isn't the most efficient way though, but I'm sure you can see how it can be improved..
|
| « Last Edit: Dec 7th, 2003, 8:30am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Traversing a Binary Tree
« Reply #16 on: Dec 7th, 2003, 10:04am » |
Quote Modify
|
Here's a solution that works for 1) when there is a solution
::
{pre, post} = args;
l = length(pre);
if (l > 1)
i = pre[2] in post;
return {pre[1],
this:verb32(pre[2..i+1], post[1..i]),
this:verb32(pre[i+2..$],post[i+1..$-1])};
else
return pre[1];
endif
::
(And like the last one, the efficiency depends on how 'in' is implemented, with the right O(n) preprocessing 'in' can be O(1) )
|
| « Last Edit: Dec 7th, 2003, 10:05am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Corleone
Newbie
Posts: 3
|
|
Re: Traversing a Binary Tree
« Reply #17 on: Feb 12th, 2004, 9:35pm » |
Quote Modify
|
I realize that the preorder-sequence of a binary search tree is one of the possible input sequences to get the same binary search tree. So, the solution of the 3rd problem can be a series of insert operations called upon the pre-order sequence to restore the tree.
Btw, as somebody pointed out the complexity would still remain the same as O(nlogn) for average and O(n^2) for the worst case.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
.