tag:blogger.com,1999:blog-6314876008291942531.post48731571977764963..comments2024-01-14T00:36:43.430-08:00Comments on Antonio Gulli's coding playground: Convert a BST into a double linked listUnknownnoreply@blogger.comBlogger1125tag:blogger.com,1999:blog-6314876008291942531.post-28983429348969907502012-10-02T13:38:05.654-07:002012-10-02T13:38:05.654-07:00public class Node {
public Node left, right, ne...public class Node {<br /> public Node left, right, next, prev;<br />}<br /><br />int MIN = 0;<br />int MAX = 1;<br />public static Node bstToList(Node n, int minOrMax) {<br /><br /> if (n == null) return null;<br /> <br /> Node maxMin = bstToList(n.left, MAX);<br /> Node minMax = bstToList(n.right, MIN);<br /><br /> if (maxMin != null) {<br /> maxMin.next = n;<br /> n.prev = maxMin;<br /> }<br /><br /> if (minMax != null) {<br /> n.next = minMax;<br /> minMax.prev = n;<br /> }<br /><br /> if (minOrMax == MAX) return findMax(n);<br /> if (minOrMax == MIN) return findMin(n);<br /><br />}<br /><br />public static void main() {<br /> Node root = generateBST();<br /> Node head = bstToList(root, MIN);<br />}<br /><br />The methods findMax and findMin simply scan the input list rightward or leftward (respectively) in order to find the absolute Max or Min.<br /><br />This implementation seems to be O(n^2) due to findMin/Max functions. I think it is easy to keep track of the abs. min and max and transform the whole algo in a O(n) solution.<br /><br />As further note, I could have used the "left" and "right" pointers to keep track of the next and prev elements in the double liked list. In this case I would have literally changed the BST to a double linked list.<br />But this way I think the implementation is clearer and I preserve the BST structure as well as the double linked list.<br /><br />Hope this works! :)<br /><br /><br /><br /><br /><br />Claudio Corsihttps://www.blogger.com/profile/13435215356783747956noreply@blogger.com