BSTtoDoublyLinkedList.java

Latest commit

History

58 lines (51 loc) * 1.42 KB

package tree;

/**

* Created by gouthamvidyapradhan on 23/01/2018. Convert a BST to a sorted circular doubly-linked

* list in-place. Think of the left and right pointers as synonymous to the previous and next

* pointers in a doubly-linked list.

Solution: Do a preorder traversal, keep track of previous node at every step and construct the

* dd-linked list in-place.

public class BSTtoDoublyLinkedList {

static class Node {

public int val;

public Node left;

public Node right;

public Node() {}

public Node(int _val, Node _left, Node _right) {

val = _val;

left = _left;

right = _right;

}

/**

* Main method

* @param args

* @throws Exception

public static void main(String[] args) throws Exception {

Node root = new Node(4, new Node(2, null, null), new Node(5, null, null));

Node result = new BSTtoDoublyLinkedList().treeToDoublyList(root);

// print result

}

public Node treeToDoublyList(Node root) {

if (root == null) return null;

Node head = new Node();

Node last = preorder(root, head);

last.right = head.right;

head.right.left = last;

return head.right;

}

Node preorder(Node node, Node prev) {

if (node == null) return prev;

else {

Node left = preorder(node.left, prev);

left.right = node;

node.left = left;

return preorder(node.right, node);

}

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

BSTtoDoublyLinkedList.java

Latest commit

History

BSTtoDoublyLinkedList.java

File metadata and controls

FilesExpand file tree

BSTtoDoublyLinkedList.java

Latest commit

History

BSTtoDoublyLinkedList.java

File metadata and controls