How to recover a binary tree from a traversal?
-
Hello I have a pre-order traversal of a binary tree stored in an array and I want to recover the tree.
I know it's impossible with one traversal only but I have more info.
For every node retrieved from the array I can use a function to get how many children (0, 1 or 2) that node has.
In addition, if a node has only 1 child, that must be its left child.
I think that's enough info to recover the tree. But I tried various ways and can't find a good solution.
Any suggestions?
Here is an easy example. The data for this tree would look like G2-D2-A0-F1-E0-M2-H0-Z0
-
Hello I have a pre-order traversal of a binary tree stored in an array and I want to recover the tree.
I know it's impossible with one traversal only but I have more info.
For every node retrieved from the array I can use a function to get how many children (0, 1 or 2) that node has.
In addition, if a node has only 1 child, that must be its left child.
I think that's enough info to recover the tree. But I tried various ways and can't find a good solution.
Any suggestions?
Here is an easy example. The data for this tree would look like G2-D2-A0-F1-E0-M2-H0-Z0
@MasterBlade Is it a binary search tree? I mean is left_node <= current_node < right_node?
If this is the case: is the array sorted?
If the answers to both questions are yes, then you can implement it like a binary search: start in the middle, the value in the middle will be root node. Then you can recursively call same function for left and for right parts of the array and so on. This is an exercise I asked candidates in our company during interviews :-) -
@MasterBlade Is it a binary search tree? I mean is left_node <= current_node < right_node?
If this is the case: is the array sorted?
If the answers to both questions are yes, then you can implement it like a binary search: start in the middle, the value in the middle will be root node. Then you can recursively call same function for left and for right parts of the array and so on. This is an exercise I asked candidates in our company during interviews :-)@jsulm said in How to recover a binary tree from a traversal?:
@MasterBlade Is it a binary search tree? I mean is left_node <= current_node < right_node?
If this is the case: is the array sorted?
If the answers to both questions are yes, then you can implement it like a binary search: start in the middle, the value in the middle will be root node. Then you can recursively call same function for left and for right parts of the array and so on. This is an exercise I asked candidates in our company during interviews :-)Thank you for the quick reply!
I'm sorry I have to answer no to both questions. :-(
Actually each node on the tree has some specific meaning. These IDs are corresponding to different functionalities.
You can see from this program that there is a logic structure in the tree. It's not a basic data stream and cannot be sorted.
What I actually stored on the disk is a sequence of 1.34.60.0.101 which is a preorder traversal of the tree. The good news is that I know how many children a node has from its ID #. That makes things a lot easier.
-
@jsulm said in How to recover a binary tree from a traversal?:
@MasterBlade Is it a binary search tree? I mean is left_node <= current_node < right_node?
If this is the case: is the array sorted?
If the answers to both questions are yes, then you can implement it like a binary search: start in the middle, the value in the middle will be root node. Then you can recursively call same function for left and for right parts of the array and so on. This is an exercise I asked candidates in our company during interviews :-)Thank you for the quick reply!
I'm sorry I have to answer no to both questions. :-(
Actually each node on the tree has some specific meaning. These IDs are corresponding to different functionalities.
You can see from this program that there is a logic structure in the tree. It's not a basic data stream and cannot be sorted.
What I actually stored on the disk is a sequence of 1.34.60.0.101 which is a preorder traversal of the tree. The good news is that I know how many children a node has from its ID #. That makes things a lot easier.
@MasterBlade Then I would say that you need to store more information besides the actual ID values to be able to restore the tree, else I cannot see how you can know to which node a value belongs.
-
@MasterBlade Then I would say that you need to store more information besides the actual ID values to be able to restore the tree, else I cannot see how you can know to which node a value belongs.
@jsulm said in How to recover a binary tree from a traversal?:
@MasterBlade Then I would say that you need to store more information besides the actual ID values to be able to restore the tree, else I cannot see how you can know to which node a value belongs.
That's true. I need to call an external function to know how many children a node has. I can rebuild the whole tree on a piece of paper. But I can't find a good way to convert it to codes. Could you give me some suggestions?
-
@jsulm said in How to recover a binary tree from a traversal?:
@MasterBlade Then I would say that you need to store more information besides the actual ID values to be able to restore the tree, else I cannot see how you can know to which node a value belongs.
That's true. I need to call an external function to know how many children a node has. I can rebuild the whole tree on a piece of paper. But I can't find a good way to convert it to codes. Could you give me some suggestions?
@MasterBlade "G2-D2-A0-F1-E0-M2-H0-Z0"
To me it looks like you need to start on the left side. First node is the root. Next one is child, either left or right side depending on value. You continue this way until a node with 0 children, in which case you go one level up.
So:- Make G root
- Make D left child
- D has child A, so put it as child of D
- A does not have children go back to D
- There is child F put it as right child of D
- ...
Something like this.
-
@MasterBlade "G2-D2-A0-F1-E0-M2-H0-Z0"
To me it looks like you need to start on the left side. First node is the root. Next one is child, either left or right side depending on value. You continue this way until a node with 0 children, in which case you go one level up.
So:- Make G root
- Make D left child
- D has child A, so put it as child of D
- A does not have children go back to D
- There is child F put it as right child of D
- ...
Something like this.
@jsulm said in How to recover a binary tree from a traversal?:
@MasterBlade "G2-D2-A0-F1-E0-M2-H0-Z0"
To me it looks like you need to start on the left side. First node is the root. Next one is child, either left or right side depending on value. You continue this way until a node with 0 children, in which case you go one level up.
So:- Make G root
- Make D left child
- D has child A, so put it as child of D
- A does not have children go back to D
- There is child F put it as right child of D
- ...
Something like this.
It seems a little bit complicated, especially the "going back" part. But I can give it a try.
Is it possible for a recursion solution? -
@jsulm said in How to recover a binary tree from a traversal?:
@MasterBlade "G2-D2-A0-F1-E0-M2-H0-Z0"
To me it looks like you need to start on the left side. First node is the root. Next one is child, either left or right side depending on value. You continue this way until a node with 0 children, in which case you go one level up.
So:- Make G root
- Make D left child
- D has child A, so put it as child of D
- A does not have children go back to D
- There is child F put it as right child of D
- ...
Something like this.
It seems a little bit complicated, especially the "going back" part. But I can give it a try.
Is it possible for a recursion solution?@MasterBlade Yes, you can do it recursively
-
@MasterBlade Yes, you can do it recursively
@jsulm said in How to recover a binary tree from a traversal?:
@MasterBlade Yes, you can do it recursively
Could you give me a hint :)
-
@jsulm said in How to recover a binary tree from a traversal?:
@MasterBlade Yes, you can do it recursively
Could you give me a hint :)
@MasterBlade Well, pass current node as parent for the next, the array and current position in it to the recursive function, something like this. Please figure out the rest, I don't have time to implement it for you. Your question is not even related to Qt.
