This is one of the interesting problems that I encountered recently. Given two sequences one being an in-order traversed sequence and other being a pre-ordered traversed sequence, a binary tree has to be reconstructed out of it.
This is theoretically possible. This problem can be cracked if we form a common pattern between these two traversed values. In a pre-order traversal, the root element will always be the first element. This element when searched in an in-order traversal will have all elements to the left on the left side of the array and all elements to the right on the right side of the array.
Applying this solution recursively will give the binary tree for us. I have included a Swing UI so as to visualize the output easily.
Example,
Pre Order Sequence = A B D E C F G H I
In Order Sequence = D B E A F C H G I
I tweaked a bit from this source for UI.
The Node structureThis is theoretically possible. This problem can be cracked if we form a common pattern between these two traversed values. In a pre-order traversal, the root element will always be the first element. This element when searched in an in-order traversal will have all elements to the left on the left side of the array and all elements to the right on the right side of the array.
Applying this solution recursively will give the binary tree for us. I have included a Swing UI so as to visualize the output easily.
Example,
Pre Order Sequence = A B D E C F G H I
In Order Sequence = D B E A F C H G I
I tweaked a bit from this source for UI.
The code for UI
Hope you learnt something today along with me.
Cheers!
Braga
2 comments:
Hi Braga
I'm getting below errors by compiling all three files :
The method add(Component) in the type Container is not applicable for the arguments (BinaryTreeView) PreOrderInOrderReconstructor.java
The method getWidth() is undefined for the type BinaryTreeView BinaryTreeView.java
The method paint(Graphics) is undefined for the type Object BinaryTreeView.java
@getting heat: Did you extend the JPanel and did the necessary imports?
If you notice closely, BinaryTreeView extends JPanel.
Post a Comment