Skip to main content

Binary Tree to Binary Search Tree Conversion

Here given code implementation process.

//C Program 
//Binary Tree to Binary Search Tree Conversion
#include<stdio.h>

#include<stdlib.h>
 //structure of Binary Search Tree node
struct Node
{
  int data;
  struct Node *left, *right;
};
struct Node *insert(int data)
{
  //create dynamic memory to new binary tree node
  struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
  if (new_node != NULL)
  {
    //set data and pointer values
    new_node->data = data;
    new_node->left = NULL; //Initially node left-pointer is NULL
    new_node->right = NULL; //Initially node right-pointer is NULL
  }
  else
  {
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }
  //return reference
  return new_node;
}
void preorder(struct Node *root)
{
  if (root != NULL)
  {
    printf("  %d", root->data);
    preorder(root->left);
    preorder(root->right);
  }
}
//Get the existing Binary search tree nodes
void get_element(struct Node *root, int auxiliary[], int *index)
{
  if (root != NULL)
  {
    //add element into array
    auxiliary[( *index) ++] = root->data;
    get_element(root->left, auxiliary, index);
    get_element(root->right, auxiliary, index);
  }
}
int element_size(struct Node *root)
{
  if (root != NULL)
  {
    return element_size(root->left) + element_size(root->right) + 1;
  }
  return 0;
}
//Swap two nodes in array
void swap(int data[], int start, int end)
{
  int back_up = data[start];
  data[start] = data[end];
  data[end] = back_up;
}
int pivit(int start, int data[], int end)
{
  int temp = start - 1;
  for (int i = start; i < end; ++i)
  {
    if (data[i] < data[end])
    {
      //swap data
      swap(data, ++temp, i);
    }
  }
  swap(data, temp + 1, end);
  return temp + 1;
}
//Sort the array element using quick sort 
void quick_sort(int start, int end, int *data)
{
  if (start < end)
  {
    int pv = pivit(start, data, end);
    quick_sort(start, pv - 1, data);
    quick_sort(pv + 1, end, data);
  }
}
void replace(struct Node *root, int *auxiliary, int *index)
{
  if (root != NULL)
  {
    replace(root->left, auxiliary, index);
    root->data = auxiliary[( *index) ++];
    replace(root->right, auxiliary, index);
  }
}
void bst(struct Node *root)
{
  int size = element_size(root);
  //Create an array which are store the BT elements
  int auxiliary[size];
  int index = 0;
  //Get all array elements
  get_element(root, auxiliary, & index);
  //sort element
  quick_sort(0, size - 1, auxiliary);
  index = 0;
  //Change sort element
  replace(root, auxiliary, & index);
}
int main()
{
  struct Node *root = NULL;
  /* Make A Binary Tree
  -----------------------
           1
         /   \
        2     3
       / \   / \
      4   5 6   7
         /   \
        8     9
  */
  //insertion of binary Tree nodes
  root = insert(1);
  root->left = insert(2);
  root->left->right = insert(5);
  root->left->right->left = insert(8);
  root->right = insert(3);
  root->right->right = insert(7);
  root->right->left = insert(6);
  root->right->left->right = insert(9);
  root->left->left = insert(4);
  printf(" Preorder \n");
  preorder(root);
  bst(root);
  printf("\n After Convert BT to BST");
  printf("\n Preorder \n");
  preorder(root);
  return 0;
}

Output

 Preorder
  1  2  4  5  8  3  6  9  7
 After Convert BT to BST
 Preorder
  5  2  1  4  3  8  6  7  9
/*
  Java Program
  Binary Tree to Binary Search Tree Conversion
*/
//Tree node
class Node
{
  public int data;
  public Node left;
  public Node right;
  public Node(int data)
  {
    //Set data value of binary tree node
    this.data = data;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree
{
  public Node root;
  public int location;
  public BinarySearchTree()
  {
    root = null;
    location = 0;
  }
  public void preorder(Node root)
  {
    if (root != null)
    {
      System.out.print(" " + root.data);
      preorder(root.left);
      preorder(root.right);
    }
  }
  //Get the existing Binary search tree nodes
  public void get_element(Node root, int[] auxiliary)
  {
    if (root != null)
    {
      //add element into array
      auxiliary[this.location] = root.data;
      this.location += 1;
      get_element(root.left, auxiliary);
      get_element(root.right, auxiliary);
    }
  }
  public int element_size(Node root)
  {
    if (root != null)
    {
      return element_size(root.left) + element_size(root.right) + 1;
    }
    return 0;
  }
  //Swap two nodes in array
  public void swap(int[] data, int start, int end)
  {
    int back_up = data[start];
    data[start] = data[end];
    data[end] = back_up;
  }
  public int pivit(int start, int[] data, int end)
  {
    int temp = start - 1;
    for (int i = start; i < end; ++i)
    {
      if (data[i] < data[end])
      {
        //swap data
        swap(data, ++temp, i);
      }
    }
    swap(data, temp + 1, end);
    return temp + 1;
  }
  //Sort the array element using quick sort 
  public void quick_sort(int start, int end, int[] data)
  {
    if (start < end)
    {
      int pv = pivit(start, data, end);
      quick_sort(start, pv - 1, data);
      quick_sort(pv + 1, end, data);
    }
  }
  public void replace(Node root, int[] auxiliary)
  {
    if (root != null)
    {
      replace(root.left, auxiliary);
      root.data = auxiliary[this.location];
      this.location += 1;
      replace(root.right, auxiliary);
    }
  }
  public void bst()
  {
    int size = element_size(root);
    //Create an array which are store the BT elements
    int[] auxiliary = new int[size];
    this.location = 0;
    //Get all array elements
    get_element(root, auxiliary);
    //sort element
    quick_sort(0, size - 1, auxiliary);
    this.location = 0;
    //Change sort element
    replace(root, auxiliary);
  }
  public static void main(String[] args)
  {
    BinarySearchTree obj = new BinarySearchTree();
    /*  Make A Binary Tree
  -----------------------
           1
         /   \
        2     3
       / \   / \
      4   5 6   7
         /   \
        8     9
  */
    //insertion of binary Tree nodes
    obj.root = new Node(1);
    obj.root.left = new Node(2);
    obj.root.left.right = new Node(5);
    obj.root.left.right.left = new Node(8);
    obj.root.right = new Node(3);
    obj.root.right.right = new Node(7);
    obj.root.right.left = new Node(6);
    obj.root.right.left.right = new Node(9);
    obj.root.left.left = new Node(4);
    System.out.print(" Preorder \n");
    obj.preorder(obj.root);
    obj.bst();
    System.out.print("\n After Convert BT to BST");
    System.out.print("\n Preorder \n");
    obj.preorder(obj.root);
  }
}

Output

 Preorder
 1 2 4 5 8 3 6 9 7
 After Convert BT to BST
 Preorder
 5 2 1 4 3 8 6 7 9
/*
  C++ Program
  Binary Tree to Binary Search Tree Conversion
*/
//Tree node
#include<iostream>

using namespace std;
class Node
{
  public: int data;
  Node * left;
  Node * right;
  Node(int data)
  {
    
    //Set data value of binary tree node
    this-> data = data;
    this->left = NULL;
    this->right = NULL;
  }
};
class BinarySearchTree
{
  public: Node * root;
  int location;
  BinarySearchTree()
  {
    this->root = NULL;
    this->location = 0;
  }
  void preorder(Node * root)
  {
    if (root != NULL)
    {
      cout << " " << root->data;
      preorder(root->left);
      preorder(root->right);
    }
  }
  //Get the existing Binary search tree nodes
  void get_element(Node * root, int auxiliary[])
  {
    if (root != NULL)
    {
      //add element into array
      auxiliary[this->location] = root->data;
      this->location += 1;
      get_element(root->left, auxiliary);
      get_element(root->right, auxiliary);
    }
  }
  int element_size(Node * root)
  {
    if (root != NULL)
    {
      return element_size(root->left) + element_size(root->right) + 1;
    }
    return 0;
  }
  //Swap two nodes in array
  void swap(int data[], int start, int end)
  {
    int back_up = data[start];
    data[start] = data[end];
    data[end] = back_up;
  }
  int pivit(int start, int data[], int end)
  {
    int temp = start - 1;
    for (int i = start; i < end; ++i)
    {
      if (data[i] < data[end])
      {
        //swap data
        swap(data, ++temp, i);
      }
    }
    swap(data, temp + 1, end);
    return temp + 1;
  }
  //Sort the array element using quick sort 
  void quick_sort(int start, int end, int data[])
  {
    if (start < end)
    {
      int pv = pivit(start, data, end);
      quick_sort(start, pv - 1, data);
      quick_sort(pv + 1, end, data);
    }
  }
  void replace(Node * root, int auxiliary[])
  {
    if (root != NULL)
    {
      replace(root->left, auxiliary);
      root->data = auxiliary[this->location];
      this->location += 1;
      replace(root->right, auxiliary);
    }
  }
  void bst()
  {
    int size = element_size(this->root);
    int auxiliary[size] ;
    this->location = 0;
    //Get all array elements
    get_element(this->root, auxiliary);
    //sort element
    quick_sort(0, size - 1, auxiliary);
    this->location = 0;
    //Change sort element
    replace(this->root, auxiliary);
  }
};
int main()
{
  BinarySearchTree obj =  BinarySearchTree();
  /*  Make A Binary Tree
    -----------------------
             1
           /   \
          2     3
         / \   / \
        4   5 6   7
           /   \
          8     9
    */
  //insertion of binary Tree nodes
  obj.root = new Node(1);
  obj.root->left = new Node(2);
  obj.root->left->right = new Node(5);
  obj.root->left->right->left = new Node(8);
  obj.root->right = new Node(3);
  obj.root->right->right = new Node(7);
  obj.root->right->left = new Node(6);
  obj.root->right->left->right = new Node(9);
  obj.root->left->left = new Node(4);
  cout << " Preorder \n";
  obj.preorder(obj.root);
  obj.bst();
  cout << "\n After Convert BT to BST";
  cout << "\n Preorder \n";
  obj.preorder(obj.root);
  return 0;
}

Output

 Preorder
 1 2 4 5 8 3 6 9 7
 After Convert BT to BST
 Preorder
 5 2 1 4 3 8 6 7 9
//Tree node
using System;
class Node
{
  public int data;
  public Node left;
  public Node right;
  public Node(int data)
  {
    //Set data value of binary tree node
    this.data = data;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree
{
  public Node root;
  public int location;
  public BinarySearchTree()
  {
    root = null;
    location = 0;
  }
  public void preorder(Node root)
  {
    if (root != null)
    {
      Console.Write(" " + root.data);
      preorder(root.left);
      preorder(root.right);
    }
  }
  //Get the existing Binary search tree nodes
  public void get_element(Node root, int[] auxiliary)
  {
    if (root != null)
    {
      //add element into array
      auxiliary[this.location] = root.data;
      this.location += 1;
      get_element(root.left, auxiliary);
      get_element(root.right, auxiliary);
    }
  }
  public int element_size(Node root)
  {
    if (root != null)
    {
      return element_size(root.left) + element_size(root.right) + 1;
    }
    return 0;
  }
  //Swap two nodes in array
  public void swap(int[] data, int start, int end)
  {
    int back_up = data[start];
    data[start] = data[end];
    data[end] = back_up;
  }
  public int pivit(int start, int[] data, int end)
  {
    int temp = start - 1;
    for (int i = start; i < end; ++i)
    {
      if (data[i] < data[end])
      {
        //swap data
        swap(data, ++temp, i);
      }
    }
    swap(data, temp + 1, end);
    return temp + 1;
  }
  //Sort the array element using quick sort 
  public void quick_sort(int start, int end, int[] data)
  {
    if (start < end)
    {
      int pv = pivit(start, data, end);
      quick_sort(start, pv - 1, data);
      quick_sort(pv + 1, end, data);
    }
  }
  public void replace(Node root, int[] auxiliary)
  {
    if (root != null)
    {
      replace(root.left, auxiliary);
      root.data = auxiliary[this.location];
      this.location += 1;
      replace(root.right, auxiliary);
    }
  }
  public void bst()
  {
    int size = element_size(root);
    int[] auxiliary = new int[size];
    this.location = 0;
    //Get all array elements
    get_element(root, auxiliary);
    //sort element
    quick_sort(0, size - 1, auxiliary);
    this.location = 0;
    //Change sort element
    replace(root, auxiliary);
  }
  public static void Main(String[] args)
  {
    BinarySearchTree obj = new BinarySearchTree();
    //insertion of binary Tree nodes
    obj.root = new Node(1);
    obj.root.left = new Node(2);
    obj.root.left.right = new Node(5);
    obj.root.left.right.left = new Node(8);
    obj.root.right = new Node(3);
    obj.root.right.right = new Node(7);
    obj.root.right.left = new Node(6);
    obj.root.right.left.right = new Node(9);
    obj.root.left.left = new Node(4);
    Console.Write(" Preorder \n");
    obj.preorder(obj.root);
    obj.bst();
    Console.Write("\n After Convert BT to BST");
    Console.Write("\n Preorder \n");
    obj.preorder(obj.root);
  }
}

Output

 Preorder
 1 2 4 5 8 3 6 9 7
 After Convert BT to BST
 Preorder
 5 2 1 4 3 8 6 7 9
<?php
/*
  Php Program
  Binary Tree to Binary Search Tree Conversion
*/
//Tree node
class Node
{
  public $data;
  public $left;
  public $right;

  function __construct($data)
  {
    //Set data value of binary tree node
    $this->data = $data;
    $this->left = null;
    $this->right = null;
  }
}
class BinarySearchTree
{
  public $root;
  public $location;

  function __construct()
  {
    $this->root = null;
    $this->location = 0;
  }

  function preorder($root)
  {
    if ($root != null)
    {
      echo " ". $root->data;
      $this->preorder($root->left);
      $this->preorder($root->right);
    }
  }
  //Get the existing Binary search tree nodes
  function get_element($root, & $auxiliary)
  {
    if ($root != null)
    {
      //add element into array
      $auxiliary[$this->location] = $root->data;
      $this->location += 1;
      $this->get_element($root->left, $auxiliary);
      $this->get_element($root->right, $auxiliary);
    }
  }

  function element_size($root)
  {
    if ($root != null)
    {
      return $this->element_size($root->left) + $this->element_size($root->right) + 1;
    }
    return 0;
  }
  //Swap two nodes in array
  function swap( & $data, $start, $end)
  {
    $back_up = $data[$start];
    $data[$start] = $data[$end];
    $data[$end] = $back_up;
  }

  function pivit($start, & $data, $end)
  {
    $temp = $start - 1;
    for ($i = $start; $i < $end; ++$i)
    {
      if ($data[$i] < $data[$end])
      {
        //swap data
        $temp += 1;
        $this->swap($data, $temp, $i);
      }
    }
    $this->swap($data, $temp + 1, $end);
    return $temp + 1;
  }
  //Sort the array element using quick sort 
  function quick_sort($start, $end, & $data)
  {
    if ($start < $end)
    {
      $pv = $this->pivit($start, $data, $end);
      $this->quick_sort($start, $pv - 1, $data);
      $this->quick_sort($pv + 1, $end, $data);
    }
  }

  function replace($root, & $auxiliary)
  {
    if ($root != null)
    {
      $this->replace($root->left, $auxiliary);
      $root->data = $auxiliary[$this->location];
      $this->location += 1;
      $this->replace($root->right, $auxiliary);
    }
  }

  function bst()
  {
    $size = $this->element_size($this->root);
    //Create an array which are store the BT elements
    $auxiliary = array_fill(0, $size, null);
    $this->location = 0;
    //Get all array elements
    $this->get_element($this->root, $auxiliary);
    //sort element
    $this->quick_sort(0, $size - 1, $auxiliary);
    $this->location = 0;
    //Change sort element
    $this->replace($this->root, $auxiliary);
  }
}

function main()
{
  $obj = new BinarySearchTree();
  //insertion of binary Tree nodes
  $obj->root = new Node(1);
  $obj->root->left = new Node(2);
  $obj->root->left->right = new Node(5);
  $obj->root->left->right->left = new Node(8);
  $obj->root->right = new Node(3);
  $obj->root->right->right = new Node(7);
  $obj->root->right->left = new Node(6);
  $obj->root->right->left->right = new Node(9);
  $obj->root->left->left = new Node(4);
  echo " Preorder \n";
  $obj->preorder($obj->root);
  $obj->bst();
  echo "\n After Convert BT to BST";
  echo "\n Preorder \n";
  $obj->preorder($obj->root);
}
main();

Output

 Preorder
 1 2 4 5 8 3 6 9 7
 After Convert BT to BST
 Preorder
 5 2 1 4 3 8 6 7 9
/*
  Node Js Program
  Binary Tree to Binary Search Tree Conversion
*/
//Tree node
class Node
{
  constructor(data)
  {
    //Set data value of binary tree node
    this.data = data;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree
{
  constructor()
  {
    this.root = null;
    this.location = 0;
  }
  preorder(root)
  {
    if (root != null)
    {
      process.stdout.write(" " + root.data);
      this.preorder(root.left);
      this.preorder(root.right);
    }
  }
  //Get the existing Binary search tree nodes
  get_element(root, auxiliary)
  {
    if (root != null)
    {
      //add element into array
      auxiliary[this.location] = root.data;
      this.location += 1;
      this.get_element(root.left, auxiliary);
      this.get_element(root.right, auxiliary);
    }
  }
  element_size(root)
  {
    if (root != null)
    {
      return this.element_size(root.left) + this.element_size(root.right) + 1;
    }
    return 0;
  }
  //Swap two nodes in array
  swap(data, start, end)
  {
    var back_up = data[start];
    data[start] = data[end];
    data[end] = back_up;
  }
  pivit(start, data, end)
  {
    var temp = start - 1;
    for (var i = start; i < end; ++i)
    {
      if (data[i] < data[end])
      {
        //swap data
        temp += 1;
        this.swap(data, temp, i);
      }
    }
    this.swap(data, temp + 1, end);
    return temp + 1;
  }
  //Sort the array element using quick sort 
  quick_sort(start, end, data)
  {
    if (start < end)
    {
      var pv = this.pivit(start, data, end);
      this.quick_sort(start, pv - 1, data);
      this.quick_sort(pv + 1, end, data);
    }
  }
  replace(root, auxiliary)
  {
    if (root != null)
    {
      this.replace(root.left, auxiliary);
      root.data = auxiliary[this.location];
      this.location += 1;
      this.replace(root.right, auxiliary);
    }
  }
  bst()
  {
    var size = this.element_size(this.root);
    //Create an array which are store the BT elements
    var auxiliary = Array(size).fill(null);
    this.location = 0;
    //Get all array elements
    this.get_element(this.root, auxiliary);
    //sort element
    this.quick_sort(0, size - 1, auxiliary);
    this.location = 0;
    //Change sort element
    this.replace(this.root, auxiliary);
  }
}

function main()
{
  var obj = new BinarySearchTree();
  /*  Make A Binary Tree
    -----------------------
             1
           /   \
          2     3
         / \   / \
        4   5 6   7
           /   \
          8     9
    */
  //insertion of binary Tree nodes
  obj.root = new Node(1);
  obj.root.left = new Node(2);
  obj.root.left.right = new Node(5);
  obj.root.left.right.left = new Node(8);
  obj.root.right = new Node(3);
  obj.root.right.right = new Node(7);
  obj.root.right.left = new Node(6);
  obj.root.right.left.right = new Node(9);
  obj.root.left.left = new Node(4);
  process.stdout.write(" Preorder \n");
  obj.preorder(obj.root);
  obj.bst();
  process.stdout.write("\n After Convert BT to BST");
  process.stdout.write("\n Preorder \n");
  obj.preorder(obj.root);
}
main();

Output

 Preorder
 1 2 4 5 8 3 6 9 7
 After Convert BT to BST
 Preorder
 5 2 1 4 3 8 6 7 9
#   Python 3 Program
#   Binary Tree to Binary Search Tree Conversion

# Tree node
class Node :
  
  def __init__(self, data) :
    # Set data value of binary tree node
    self.data = data
    self.left = None
    self.right = None
  

class BinarySearchTree :
  
  def __init__(self) :
    self.root = None
    self.location = 0
  
  def preorder(self, root) :
    if (root != None) :
      print(" ", root.data, end = "")
      self.preorder(root.left)
      self.preorder(root.right)
    
  
  # Get the existing Binary search tree nodes
  def get_element(self, root, auxiliary) :
    if (root != None) :
      # add element into array
      auxiliary[self.location] = root.data
      self.location += 1
      self.get_element(root.left, auxiliary)
      self.get_element(root.right, auxiliary)
    
  
  def element_size(self, root) :
    if (root != None) :
      return self.element_size(root.left) + self.element_size(root.right) + 1
    
    return 0
  
  # Swap two nodes in array
  def swap(self, data, start, last) :
    back_up = data[start]
    data[start] = data[last]
    data[last] = back_up
  
  def pivit(self, start, data, last) :
    temp = start - 1
    i = start
    while (i < last) :
      if (data[i] < data[last]) :
        # swap data
        temp += 1
        self.swap(data, temp, i)
      
      i += 1
    
    self.swap(data, temp + 1, last)
    return temp + 1
  
  # Sort the array element using quick sort 
  def quick_sort(self, start, last, data) :
    if (start < last) :
      pv = self.pivit(start, data, last)
      self.quick_sort(start, pv - 1, data)
      self.quick_sort(pv + 1, last, data)
    
  
  def replace(self, root, auxiliary) :
    if (root != None) :
      self.replace(root.left, auxiliary)
      root.data = auxiliary[self.location]
      self.location += 1
      self.replace(root.right, auxiliary)
    
  
  def bst(self) :
    size = self.element_size(self.root)
    # Create an array which are store the BT elements
    auxiliary = [None] * size
    self.location = 0
    # Get all array elements
    self.get_element(self.root, auxiliary)
    # sort element
    self.quick_sort(0, size - 1, auxiliary)
    self.location = 0
    # Change sort element
    self.replace(self.root, auxiliary)
  

def main() :
  obj = BinarySearchTree()
  # insertion of binary Tree nodes
  #   Make A Binary Tree
  #       -----------------------
  #                1
  #              /   \
  #             2     3
  #            / \   / \
  #           4   5 6   7
  #              /   \
  #             8     9
  #       
  
  obj.root = Node(1)
  obj.root.left = Node(2)
  obj.root.left.right = Node(5)
  obj.root.left.right.left = Node(8)
  obj.root.right = Node(3)
  obj.root.right.right = Node(7)
  obj.root.right.left = Node(6)
  obj.root.right.left.right = Node(9)
  obj.root.left.left = Node(4)
  print(" Preorder \n", end = "")
  obj.preorder(obj.root)
  obj.bst()
  print("\n After Convert BT to BST", end = "")
  print("\n Preorder \n", end = "")
  obj.preorder(obj.root)

if __name__ == "__main__": main()

Output

 Preorder
  1  2  4  5  8  3  6  9  7
 After Convert BT to BST
 Preorder
  5  2  1  4  3  8  6  7  9
#   Ruby Program
#   Binary Tree to Binary Search Tree Conversion

# Tree node
class Node 

  # Define the accessor and reader of class Node  
  attr_reader :data, :left, :right
  attr_accessor :data, :left, :right

  def initialize(data)
  
    # Set data value of binary tree node
    self.data = data
    self.left = nil
    self.right = nil
  end
end
class BinarySearchTree 

  # Define the accessor and reader of class BinarySearchTree  
  attr_reader :root, :location
  attr_accessor :root, :location

  def initialize()
  
    @root = nil
    @location = 0
  end
  def preorder(root)
  
    if (root != nil)
    
      print(" ", root.data)
      self.preorder(root.left)
      self.preorder(root.right)
    end
  end
  # Get the existing Binary search tree nodes
  def get_element(root, auxiliary)
  
    if (root != nil)
    
      # add element into array
      auxiliary[self.location] = root.data
      self.location += 1
      self.get_element(root.left, auxiliary)
      self.get_element(root.right, auxiliary)
    end
  end
  def element_size(root)
  
    if (root != nil)
    
      return self.element_size(root.left) + self.element_size(root.right) + 1
    end
    return 0
  end
  # Swap two nodes in array
  def swap(data, start, last)
  
    back_up = data[start]
    data[start] = data[last]
    data[last] = back_up
  end
  def pivit(start, data, last)
  
    temp = start - 1
    i = start
    while (i < last)
    
      if (data[i] < data[last])
      
        # swap data
        temp += 1
        self.swap(data, temp, i)
      end
      i += 1
    end
    self.swap(data, temp + 1, last)
    return temp + 1
  end
  # Sort the array element using quick sort 
  def quick_sort(start, last, data)
  
    if (start < last)
    
      pv = self.pivit(start, data, last)
      self.quick_sort(start, pv - 1, data)
      self.quick_sort(pv + 1, last, data)
    end
  end
  def replace(root, auxiliary)
  
    if (root != nil)
    
      self.replace(root.left, auxiliary)
      root.data = auxiliary[self.location]
      self.location += 1
      self.replace(root.right, auxiliary)
    end
  end
  def bst()
  
    size = self.element_size(@root)
    # Create an array which are store the BT elements
    auxiliary = Array.new(size) {nil}
    self.location = 0
    # Get all array elements
    self.get_element(@root, auxiliary)
    # sort element
    self.quick_sort(0, size - 1, auxiliary)
    self.location = 0
    # Change sort element
    self.replace(@root, auxiliary)
  end
end
def main()

  obj = BinarySearchTree.new()
  # insertion of binary Tree nodes
  #   Make A Binary Tree
  #       -----------------------
  #                1
  #              /   \
  #             2     3
  #            / \   / \
  #           4   5 6   7
  #              /   \
  #             8     9
  #       
  
  obj.root = Node.new(1)
  obj.root.left = Node.new(2)
  obj.root.left.right = Node.new(5)
  obj.root.left.right.left = Node.new(8)
  obj.root.right = Node.new(3)
  obj.root.right.right = Node.new(7)
  obj.root.right.left = Node.new(6)
  obj.root.right.left.right = Node.new(9)
  obj.root.left.left = Node.new(4)
  print(" Preorder \n")
  obj.preorder(obj.root)
  obj.bst()
  print("\n After Convert BT to BST")
  print("\n Preorder \n")
  obj.preorder(obj.root)
end
main()

Output

 Preorder 
 1 2 4 5 8 3 6 9 7
 After Convert BT to BST
 Preorder 
 5 2 1 4 3 8 6 7 9
/*
  Scala Program
  Binary Tree to Binary Search Tree Conversion
*/
//Tree node
class Node(var data: Int,
  var left: Node,
    var right: Node)
{
  def this(data: Int)
  {
    //Set data value of binary tree node
    this(data,null,null);
  }
}
class BinarySearchTree(var root: Node,
  var location: Int)
{
  def this()
  {
    this(null,0);
  }
  def preorder(root: Node): Unit = {
    if (root != null)
    {
      print(" " + root.data);
      preorder(root.left);
      preorder(root.right);
    }
  }
  //Get the existing Binary search tree nodes
  def get_element(root: Node, auxiliary: Array[Int]): Unit = {
    if (root != null)
    {
      //add element into array
      auxiliary(this.location) = root.data;
      this.location += 1;
      get_element(root.left, auxiliary);
      get_element(root.right, auxiliary);
    }
  }
  def element_size(root: Node): Int = {
    if (root != null)
    {
      return element_size(root.left) + element_size(root.right) + 1;
    }
    return 0;
  }
  //Swap two nodes in array
  def swap(data: Array[Int], start: Int, last: Int): Unit = {
    var back_up: Int = data(start);
    data(start) = data(last);
    data(last) = back_up;
  }
  def pivit(start: Int, data: Array[Int], last: Int): Int = {
    var temp: Int = start - 1;
    var i: Int = start;
    while (i < last)
    {
      if (data(i) < data(last))
      {
        //swap data
        temp += 1;
        swap(data, temp, i);
      }
      i += 1;
    }
    swap(data, temp + 1, last);
    return temp + 1;
  }
  //Sort the array element using quick sort 
  def quick_sort(start: Int, last: Int, data: Array[Int]): Unit = {
    if (start < last)
    {
      var pv: Int = pivit(start, data, last);
      quick_sort(start, pv - 1, data);
      quick_sort(pv + 1, last, data);
    }
  }
  def replace(root: Node, auxiliary: Array[Int]): Unit = {
    if (root != null)
    {
      replace(root.left, auxiliary);
      root.data = auxiliary(this.location);
      this.location += 1;
      replace(root.right, auxiliary);
    }
  }
  def bst(): Unit = {
    var size: Int = element_size(root);
    //Create an array which are store the BT elements
    var auxiliary: Array[Int] = Array.fill[Int](size)(0);
    this.location = 0;
    //Get all array elements
    get_element(root, auxiliary);
    //sort element
    quick_sort(0, size - 1, auxiliary);
    this.location = 0;
    //Change sort element
    replace(root, auxiliary);
  }
}
object Main
{
  def main(args: Array[String]): Unit = {
    var obj: BinarySearchTree = new BinarySearchTree();
    //insertion of binary Tree nodes
    /*  Make A Binary Tree
          -----------------------
                   1
                 /   \
                2     3
               / \   / \
              4   5 6   7
                 /   \
                8     9
          */
    obj.root = new Node(1);
    obj.root.left = new Node(2);
    obj.root.left.right = new Node(5);
    obj.root.left.right.left = new Node(8);
    obj.root.right = new Node(3);
    obj.root.right.right = new Node(7);
    obj.root.right.left = new Node(6);
    obj.root.right.left.right = new Node(9);
    obj.root.left.left = new Node(4);
    print(" Preorder \n");
    obj.preorder(obj.root);
    obj.bst();
    print("\n After Convert BT to BST");
    print("\n Preorder \n");
    obj.preorder(obj.root);
  }
}

Output

 Preorder
 1 2 4 5 8 3 6 9 7
 After Convert BT to BST
 Preorder
 5 2 1 4 3 8 6 7 9
/*
  Swift Program
  Binary Tree to Binary Search Tree Conversion
*/
//Tree node
class Node
{
  var data: Int;
  var left: Node? ;
  var right: Node? ;
  init(_ data: Int)
  {
    //Set data value of binary tree node
    self.data = data;
    self.left = nil;
    self.right = nil;
  }
}
class BinarySearchTree
{
  var root: Node? ;
  var location: Int;
  init()
  {
    self.root = nil;
    self.location = 0;
  }
  func preorder(_ root: Node? )
  {
    if (root != nil)
    {
      print(" ", root!.data, terminator: "");
      self.preorder(root!.left);
      self.preorder(root!.right);
    }
  }
  //Get the existing Binary search tree nodes
  func get_element(_ root: Node? , _ auxiliary : inout[Int])
  {
    if (root != nil)
    {
      //add element into array
      auxiliary[self.location] = root!.data;
      self.location += 1;
      self.get_element(root!.left, &auxiliary);
      self.get_element(root!.right, &auxiliary);
    }
  }
  func element_size(_ root: Node? ) -> Int
  {
    if (root != nil)
    {
      return self.element_size(root!.left) + self.element_size(root!.right) + 1;
    }
    return 0;
  }
  //Swap two nodes in array
  func swap(_ data: inout[Int], _ start: Int, _ last: Int)
  {
    let back_up: Int = data[start];
    data[start] = data[last];
    data[last] = back_up;
  }
  func pivit(_ start: Int, _ data: inout[Int], _ last: Int) -> Int
  {
    var temp: Int = start - 1;
    var i: Int = start;
    while (i < last)
    {
      if (data[i] < data[last])
      {
        //swap data
        temp += 1;
        self.swap(&data, temp, i);
      }
      i += 1;
    }
    self.swap(&data, temp + 1, last);
    return temp + 1;
  }
  //Sort the array element using quick sort 
  func quick_sort(_ start: Int, _ last: Int, _ data: inout[Int])
  {
    if (start < last)
    {
      let pv: Int = self.pivit(start, &data, last);
      self.quick_sort(start, pv - 1, &data);
      self.quick_sort(pv + 1, last, &data);
    }
  }
  func replace(_ root: Node? , _ auxiliary : inout[Int])
  {
    if (root != nil)
    {
      self.replace(root!.left, &auxiliary);
      root!.data = auxiliary[self.location];
      self.location += 1;
      self.replace(root!.right, &auxiliary);
    }
  }
  func bst()
  {
    let size: Int = self.element_size(self.root);
    //Create an array which are store the BT elements
    var auxiliary: [Int] = Array(repeating: 0, count: size);
    self.location = 0;
    //Get all array elements
    self.get_element(self.root, &auxiliary);
    //sort element
    self.quick_sort(0, size - 1, &auxiliary);
    self.location = 0;
    //Change sort element
    self.replace(self.root, &auxiliary);
  }
}
func main()
{
  let obj: BinarySearchTree = BinarySearchTree();
  //insertion of binary Tree nodes
  /*  Make A Binary Tree
        -----------------------
                 1
               /   \
              2     3
             / \   / \
            4   5 6   7
               /   \
              8     9
        */
  obj.root = Node(1);
  obj.root!.left = Node(2);
  obj.root!.left!.right = Node(5);
  obj.root!.left!.right!.left = Node(8);
  obj.root!.right = Node(3);
  obj.root!.right!.right = Node(7);
  obj.root!.right!.left = Node(6);
  obj.root!.right!.left!.right = Node(9);
  obj.root!.left!.left = Node(4);
  print(" Preorder \n", terminator: "");
  obj.preorder(obj.root);
  obj.bst();
  print("\n After Convert BT to BST", terminator: "");
  print("\n Preorder \n", terminator: "");
  obj.preorder(obj.root);
}
main();

Output

 Preorder
  1  2  4  5  8  3  6  9  7
 After Convert BT to BST
 Preorder
  5  2  1  4  3  8  6  7  9
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment