Sorted array to balanced BST

Sorted array to balanced BST

Here given code implementation process.

//C Program 
//Sorted array to balanced bst
#include<stdio.h>
#include<stdlib.h>
//Structure of Binary Search Tree node
struct Node
{
  int data;
  struct Node *left,*right; 
};

void preorder(struct Node*root)
{
  if(root!=NULL)
  {
    printf("%3d ",root->data );
    preorder(root->left);

    preorder(root->right);
  }
}
void inorder(struct Node*root)
{
  if(root!=NULL)
  {
    
    inorder(root->left);
    printf("%3d ",root->data );
    inorder(root->right);
  }
}
void postorder(struct Node*root)
{
  if(root!=NULL)
  {
    
    postorder(root->left);

    postorder(root->right);

    printf("%3d ",root->data );
  }
}
struct Node* make_bst(int start,int end,int arr[],int size)
{
  if(start > end || end < 0 || end >= size)
  {
    return NULL;
  }

  int middle = start + (end-start)/2;

  struct Node*root= (struct Node *)malloc(sizeof(struct Node ));

  root->data = arr[middle];
  root->left = make_bst(start,middle-1,arr,size); 
  root->right = make_bst(middle+1,end,arr,size);

  return root;

}
int main(){
    


  int arr[]={1,2,4,5,6,7,8,9,11,13};

  int size=sizeof(arr)/sizeof(arr[0]);
  
  struct Node*root = NULL;

  //Created binary search tree
  /*
           6
        /    \
       2       9
      / \     /  \
     1   4   7    11
          \   \    \
           5   8    13
  */
  /* Preorder 
  6   2   1   4   5   9   7   8  11  13 
 Inorder 
  1   2   4   5   6   7   8   9  11  13 
 Postorder 
  1   5   4   2   8   7  13  11   9   6 */


  //address of first node are assigning to root
  root=make_bst(0,size-1,arr,size);



  printf(" Preorder \n");
  preorder(root);

  printf("\n Inorder \n");
  inorder(root);

  printf("\n Postorder \n");
  postorder(root);

  return 0;
}

Output

 Preorder 
  6   2   1   4   5   9   7   8  11  13 
 Inorder 
  1   2   4   5   6   7   8   9  11  13 
 Postorder 
  1   5   4   2   8   7  13  11   9   6
/*
  C++ Program
  Sorted array to balanced bst
*/
#include<iostream>

using namespace std;
class Node {
  public:
  int data;
  Node *left;
  Node *right;
  Node(int value) {
    this->data = value;
    this->left = NULL;
    this->right = NULL;
  }
};
class BinarySearchTree {
public:
  Node *root;
  BinarySearchTree() {
    this->root = NULL;
  }
  void preorder(Node *head) {
    if (head != NULL) {
      cout << head->data << "  ";
      this->preorder(head->left);
      this->preorder(head->right);
    }
  }
  void inorder(Node *head) {
    if (head != NULL) {
      this->inorder(head->left);
      cout << head->data << "  ";
      this->inorder(head->right);
    }
  }
  void postorder(Node *head) {
    if (head != NULL) {
      this->postorder(head->left);
      this->postorder(head->right);
      cout << head->data << "  ";
    }
  }
  Node *balance_bst(int start, int end, int arr[], int size) {
    if (start > end || end < 0 || end >= size) {
      return NULL;
    }
    int middle = start + (end - start) / 2;
    Node *new_node = new Node(arr[middle]);
    new_node->left = this->balance_bst(start, middle - 1, arr, size);
    new_node->right = this->balance_bst(middle + 1, end, arr, size);
    return new_node;
  }
};

int main() {
  BinarySearchTree obj;
  
  int arr[] = {1,2,4,5,6,7,8,9,11,13};

  int size = sizeof(arr)/sizeof(arr[0]);

  obj.root = obj.balance_bst(0, size - 1, arr, size);
  /*
           6
        /    \
       2       9
      / \     /  \
     1   4   7    11
          \   \    \
           5   8    13
  */
  cout << (" Preorder \n");
  obj.preorder(obj.root);
  cout << ("\n Inorder \n");
  obj.inorder(obj.root);
  cout << ("\n Postorder \n");
  obj.postorder(obj.root);
  return 0;
}

Output

 Preorder 
  6   2   1   4   5   9   7   8  11  13 
 Inorder 
  1   2   4   5   6   7   8   9  11  13 
 Postorder 
  1   5   4   2   8   7  13  11   9   6
//Java program
//Sorted array to balanced bst

class Node {
  public int data;
  public Node left;
  public Node right;

  public Node(int value) {
    data = value;
    left = null;
    right = null;
  }
}
public class BinarySearchTree {


  public Node root;
  
  public BinarySearchTree()
  {
    root = null;
  }

  public void preorder(Node head) {
    if (head != null) {
      System.out.print(head.data + "  ");
      preorder(head.left);

      preorder(head.right);
    }
  }
  public void inorder(Node head) {
    if (head != null) {

      inorder(head.left);
      System.out.print(head.data + "  ");
      inorder(head.right);
    }
  }
  public void postorder(Node head) {
    if (head != null) {

      postorder(head.left);

      postorder(head.right);

      System.out.print(head.data + "  ");
    }
  }
  public Node balance_bst(int start, int end, int[] arr, int size) {
    if (start > end || end < 0 || end >= size) {
      return null;
    }

    int middle = start + (end - start) / 2;

    Node new_node = new Node(arr[middle]);


    new_node.left = balance_bst(start, middle - 1, arr, size);
    new_node.right = balance_bst(middle + 1, end, arr, size);

    return new_node;

  }
  public static void main(String[] args) {

    BinarySearchTree obj = new BinarySearchTree();
    //sorted array
    int[] arr = {1,2,4,5,6,7,8,9,11,13};
    
    int size = arr.length;

    obj.root = obj.balance_bst(0, size - 1, arr, size);

    /*
    Constructing BinarySearchTree

             6
          /    \
         2       9
        / \     /  \
       1   4   7    11
            \   \    \
             5   8    13
    */
    System.out.print(" Preorder \n");
    obj.preorder(obj.root);

    System.out.print("\n Inorder \n");
    obj.inorder(obj.root);

    System.out.print("\n Postorder \n");
    obj.postorder(obj.root);
  }
}

Output

 Preorder 
  6   2   1   4   5   9   7   8  11  13 
 Inorder 
  1   2   4   5   6   7   8   9  11  13 
 Postorder 
  1   5   4   2   8   7  13  11   9   6
//C# program
//Sorted array to balanced bst
using System;
public class Node {
	public int data;
	public Node left;
	public Node right;

	public Node(int value) {
		data = value;
		left = null;
		right = null;
	}
}
public class BinarySearchTree {


	public Node root;

	public BinarySearchTree()
	{
		root = null;
	}

	public void preorder(Node head) {
		if (head != null) {
			Console.Write(head.data + "  ");
			preorder(head.left);

			preorder(head.right);
		}
	}
	public void inorder(Node head) {
		if (head != null) {

			inorder(head.left);
			Console.Write(head.data + "  ");
			inorder(head.right);
		}
	}
	public void postorder(Node head) {
		if (head != null) {

			postorder(head.left);

			postorder(head.right);

			Console.Write(head.data + "  ");
		}
	}
	public Node balance_bst(int start, int end, int[] arr, int size) {
		if (start > end || end < 0 || end >= size) {
			return null;
		}

		int middle = start + (end - start) / 2;

		Node new_node = new Node(arr[middle]);


		new_node.left = balance_bst(start, middle - 1, arr, size);
		new_node.right = balance_bst(middle + 1, end, arr, size);

		return new_node;

	}
	public static void Main(String[] args) {

		BinarySearchTree obj = new BinarySearchTree();
		//sorted array
		int[] arr = {1,2,4,5,6,7,8,9,11,13};

		int size = arr.Length;

		obj.root = obj.balance_bst(0, size - 1, arr, size);

		/*
    Constructing BinarySearchTree

             6
          /    \
         2       9
        / \     /  \
       1   4   7    11
            \   \    \
             5   8    13
    */
		Console.Write(" Preorder \n");
		obj.preorder(obj.root);

		Console.Write("\n Inorder \n");
		obj.inorder(obj.root);

		Console.Write("\n Postorder \n");
		obj.postorder(obj.root);
	}
}

Output

 Preorder 
  6   2   1   4   5   9   7   8  11  13 
 Inorder 
  1   2   4   5   6   7   8   9  11  13 
 Postorder 
  1   5   4   2   8   7  13  11   9   6
# Python Program 
# Sorted array to balanced bst
class Node :

  def __init__(self, value) :
    self.data = value
    self.left = None
    self.right = None
  

class BinarySearchTree :

  def __init__(self) :
    self.root = None
  
  def preorder(self, head) :
    if (head != None) :
      print(head.data ,end="  ")
      self.preorder(head.left)
      self.preorder(head.right)
    
  
  def inorder(self, head) :
    if (head != None) :
      self.inorder(head.left)
      print(head.data ,end="  ")
      self.inorder(head.right)
    
  
  def postorder(self, head) :
    if (head != None) :
      self.postorder(head.left)
      self.postorder(head.right)
      print(head.data ,end="  ")
    
  
  def balance_bst(self, start, end, arr, size) :
    if (start > end or end < 0 or end >= size) :
      return None
    
    middle = start + int((end - start) / 2)
    new_node = Node(arr[middle])
    new_node.left = self.balance_bst(start, middle - 1, arr, size)
    new_node.right = self.balance_bst(middle + 1, end, arr, size)
    return new_node

def main() :
  obj = BinarySearchTree()
  #
  #           6
  #        /    \
  #       2       9
  #      / \     /  \
  #     1   4   7    11
  #          \   \    \
  #           5   8    13
  #  
  arr = [1, 2, 4, 5, 6, 7, 8, 9, 11, 13]
  size = len(arr)
  obj.root = obj.balance_bst(0, size - 1, arr, size)
  print(" Preorder ")
  obj.preorder(obj.root)
  print("\n Inorder ")
  obj.inorder(obj.root)
  print("\n Postorder ")
  obj.postorder(obj.root)
  

if __name__ == "__main__":
  main()

Output

 Preorder 
  6   2   1   4   5   9   7   8  11  13 
 Inorder 
  1   2   4   5   6   7   8   9  11  13 
 Postorder 
  1   5   4   2   8   7  13  11   9   6
# Ruby Program
# Sorted array to balanced bst
class Node 
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(value) 
		@data = value
		@left = nil
		@right = nil
	end
end

class BinarySearchTree 
	attr_reader :root
	attr_accessor :root
	def initialize() 
		@root = nil
	end
	def preorder(head) 
		if (head != nil) 
			print(head.data ,"  ")
			self.preorder(head.left)
			self.preorder(head.right)
		end
	end
	def inorder(head) 
		if (head != nil) 
			self.inorder(head.left)
			print(head.data ,"  ")
			self.inorder(head.right)
		end
	end
	def postorder(head) 
		if (head != nil) 
			self.postorder(head.left)
			self.postorder(head.right)
			print(head.data ,"  ")
		end
	end
	def balance_bst(start, last, arr, size) 
		if (start > last or last < 0 or last >= size) 
			return nil
		end
		middle = start + ((last - start) / 2).to_i
		new_node = Node.new(arr[middle])
		new_node.left = self.balance_bst(start, middle - 1, arr, size)
		new_node.right = self.balance_bst(middle + 1, last, arr, size)
		return new_node
	end
end
def main() 
	obj = BinarySearchTree.new()
	arr = [1, 2, 4, 5, 6, 7, 8, 9, 11, 13]
	size = arr.length
	obj.root = obj.balance_bst(0, size - 1, arr, size)
	#
	#           6
	#        /    \
	#       2       9
	#      / \     /  \
	#     1   4   7    11
	#          \   \    \
	#           5   8    13
	#  
	print(" Preorder \n")
	obj.preorder(obj.root)
	print("\n Inorder \n")
	obj.inorder(obj.root)
	print("\n Postorder \n")
	obj.postorder(obj.root)
end

main()

Output

 Preorder 
  6   2   1   4   5   9   7   8  11  13 
 Inorder 
  1   2   4   5   6   7   8   9  11  13 
 Postorder 
  1   5   4   2   8   7  13  11   9   6
<?php
/*
  Php Program
  Sorted array to balanced bst
*/
class Node {
  public $data;
  public $left;
  public $right;

  function __construct($value) {
    $this->data = $value;
    $this->left = null;
    $this->right = null;
  }
}
class BinarySearchTree {
  public $root;

  function __construct() {
    $this->root = null;
  }
  public  function preorder($head) {
    if ($head != null) {
      echo($head->data ."  ");
      $this->preorder($head->left);
      $this->preorder($head->right);
    }
  }
  public  function inorder($head) {
    if ($head != null) {
      $this->inorder($head->left);
      echo($head->data ."  ");
      $this->inorder($head->right);
    }
  }
  public  function postorder($head) {
    if ($head != null) {
      $this->postorder($head->left);
      $this->postorder($head->right);
      echo($head->data ."  ");
    }
  }
  public  function balance_bst($start, $end, $arr, $size) {
    if ($start > $end || $end < 0 || $end >= $size) {
      return null;
    }
    $middle = $start + intval(($end - $start) / 2);
    $new_node = new Node($arr[$middle]);
    $new_node->left = $this->balance_bst($start, $middle - 1, $arr, $size);
    $new_node->right = $this->balance_bst($middle + 1, $end, $arr, $size);
    return $new_node;
  }

}
function main() {
  $obj = new BinarySearchTree();
  $arr = array(1, 2, 4, 5, 6, 7, 8, 9, 11, 13);
  $size = count($arr);
  $obj->root = $obj->balance_bst(0, $size - 1, $arr, $size);
  /*
           6
        /    \
       2       9
      / \     /  \
     1   4   7    11
          \   \    \
           5   8    13
  */
  echo(" Preorder \n");
  $obj->preorder($obj->root);
  echo("\n Inorder \n");
  $obj->inorder($obj->root);
  echo("\n Postorder \n");
  $obj->postorder($obj->root);
}
main();

Output

 Preorder 
  6   2   1   4   5   9   7   8  11  13 
 Inorder 
  1   2   4   5   6   7   8   9  11  13 
 Postorder 
  1   5   4   2   8   7  13  11   9   6
/*
  Node JS Program
  Sorted array to balanced bst
*/
class Node {

	constructor(value) {
		this.data = value;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree {
	
	constructor() {
		this.root = null;
	}
	preorder(head) {
		if (head != null) {
			process.stdout.write(head.data + "  ");
			this.preorder(head.left);
			this.preorder(head.right);
		}
	}
	inorder(head) {
		if (head != null) {
			this.inorder(head.left);
			process.stdout.write(head.data + "  ");
			this.inorder(head.right);
		}
	}
	postorder(head) {
		if (head != null) {
			this.postorder(head.left);
			this.postorder(head.right);
			process.stdout.write(head.data + "  ");
		}
	}
	balance_bst(start, end, arr, size) {
		if (start > end || end < 0 || end >= size) {
			return null;
		}
		var middle = start + parseInt((end - start) / 2);
		var new_node = new Node(arr[middle]);
		new_node.left = this.balance_bst(start, middle - 1, arr, size);
		new_node.right = this.balance_bst(middle + 1, end, arr, size);
		return new_node;
	}
}

function main() {
	var obj = new BinarySearchTree();
	var arr = [1, 2, 4, 5, 6, 7, 8, 9, 11, 13];
	var size = arr.length;
	obj.root = obj.balance_bst(0, size - 1, arr, size);
	/*
           6
        /    \
       2       9
      / \     /  \
     1   4   7    11
          \   \    \
           5   8    13
    */
	process.stdout.write(" Preorder \n");
	obj.preorder(obj.root);
	process.stdout.write("\n Inorder \n");
	obj.inorder(obj.root);
	process.stdout.write("\n Postorder \n");
	obj.postorder(obj.root);
}


main();

Output

 Preorder 
  6   2   1   4   5   9   7   8  11  13 
 Inorder 
  1   2   4   5   6   7   8   9  11  13 
 Postorder 
  1   5   4   2   8   7  13  11   9   6
/*
  Swift 4 Program
  Sorted array to balanced bst
*/
class Node {
  var data: Int;
  var left: Node? ;
  var right: Node? ;
  init(_ value: Int) {
    self.data = value;
    self.left = nil;
    self.right = nil;
  }
}
class BinarySearchTree {
  var root: Node? ;
  init() {
    self.root = nil;
  }
  func preorder(_ head: Node? ) {
    if (head != nil) {
      print(head!.data, terminator : "  ");
      self.preorder(head!.left);
      self.preorder(head!.right);
    }
  }
  func inorder(_ head: Node? ) {
    if (head != nil) {
      self.inorder(head!.left);
      print(head!.data, terminator : "  ");
      self.inorder(head!.right);
    }
  }
  func postorder(_ head: Node? ) {
    if (head != nil) {
      self.postorder(head!.left);
      self.postorder(head!.right);
      print(head!.data, terminator : "  ");
    }
  }
  func balance_bst(_ start: Int, _ end: Int, _ arr: [Int], _ size : Int) -> Node? {
    if (start > end || end < 0 || end >= size) {
      return nil;
    }
    let middle: Int = start + (end - start) / 2;
    let new_node: Node? = Node(arr[middle]);
    new_node!.left = self.balance_bst(start, middle - 1, arr, size);
    new_node!.right = self.balance_bst(middle + 1, end, arr, size);
    return new_node;
  }
}
func main() {
  let obj: BinarySearchTree = BinarySearchTree();
  let arr: [Int] = [1, 2, 4, 5, 6, 7, 8, 9, 11, 13];
  let size: Int = arr.count;
  obj.root = obj.balance_bst(0, size - 1, arr, size);

  /*
           6
        /    \
       2       9
      / \     /  \
     1   4   7    11
          \   \    \
           5   8    13
  */
  print(" Preorder ");
  obj.preorder(obj.root);
  print("\n Inorder ");
  obj.inorder(obj.root);
  print("\n Postorder ");
  obj.postorder(obj.root);
}
main();

Output

 Preorder 
  6   2   1   4   5   9   7   8  11  13 
 Inorder 
  1   2   4   5   6   7   8   9  11  13 
 Postorder 
  1   5   4   2   8   7  13  11   9   6

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







© 2021, kalkicode.com, All rights reserved