// A BST node
class Node
int knowledge;
Node left, proper;
Node(int knowledge)
this.knowledge = knowledge;
this.left = this.proper = null;
// Wrapper over `Node` class
class NodeWrapper
public Node node;
NodeWrapper(Node node)
this.node = node;
class Important
// Technique to push a BST node on the entrance of a doubly linked record
public static Node push(Node root, Node head)
root.proper = head;
if (head != null)
head.left = root;
head = root;
return head;
// Technique to rely the overall variety of nodes in a doubly-linked record
public static int measurement(Node node)
int counter = 0;
whereas (node != null)
node = node.proper;
counter++;
return counter;
// Technique to print preorder traversal of the BST
public static void preorder(Node root)
if (root == null)
return;
System.out.print(root.knowledge + ” “);
preorder(root.left);
preorder(root.proper);
// Recursive technique to assemble a balanced BST from a sorted doubly linked record
public static Node convertSortedDLLToBalancedBST(NodeWrapper head, int n)
// base case
if (n <= 0)
return null;
// recursively assemble the left subtree
Node leftSubTree = convertSortedDLLToBalancedBST(head, n/2);
// `head` now factors to the center node of the sorted DDL
// make the center node of the sorted DDL as the basis node of the BST
Node root = head.node;
// replace left little one of the basis node
root.left = leftSubTree;
// replace the top reference of the doubly linked record
head.node = head.node.proper;
// recursively assemble the appropriate subtree with the remaining nodes
root.proper = convertSortedDLLToBalancedBST(head, n – (n/2 + 1));
/* +1 for the basis Node */
// return the basis node
return root;
// Recursive technique to transform a BST right into a doubly-linked record. It takes
// the BST’s root node and the top node of the doubly linked record as an argument
public static Node convertBSTtoSortedDLL(Node root, Node head)
// base case
if (root == null)
return head;
// recursively convert the appropriate subtree
head = convertBSTtoSortedDLL(root.proper, head);
// push the present node on the entrance of the doubly linked record
head = push(root, head);
// recursively convert the left subtree
head = convertBSTtoSortedDLL(root.left, head);
return head;
// Recursive technique to merge two doubly-linked lists right into a
// single doubly linked record in sorted order
public static Node sortedMerge(Node first, Node second)
// if the primary record is empty, return the second record
if (first == null)
return second;
// if the second record is empty, return the primary record
if (second == null)
return first;
// if the top node of the primary record is smaller
if (first.knowledge < second.knowledge)
first.proper = sortedMerge(first.proper, second);
first.proper.left = first;
return first;
// if the top node of the second record is smaller
else
second.proper = sortedMerge(first, second.proper);
second.proper.left = second;
return second;
// Technique to merge two balanced BSTs right into a single balanced BST
public static Node merge(Node first, Node second)
// merge each BSTs right into a sorted doubly linked record
Node head = sortedMerge(convertBSTtoSortedDLL(first, null),
convertBSTtoSortedDLL(second, null));
// assemble a balanced BST from a sorted doubly linked record
// Wrap the `head` node, so its reference may be modified contained in the perform
return convertSortedDLLToBalancedBST(new NodeWrapper(head), measurement(head));
public static void primary(String[] args)
/*
Assemble the primary BST
20
/
10 30
/
25 100
*/
Node first = new Node(20);
first.left = new Node(10);
first.proper = new Node(30);
first.proper.left = new Node(25);
first.proper.proper = new Node(100);
/*
Assemble the second BST
50
/
5 70
*/
Node second = new Node(50);
second.left = new Node(5);
second.proper = new Node(70);
// merge each BSTs
Node root = merge(first, second);
preorder(root);
