Saturday, 5 January 2019

Create a balanced Binary Search Tree (BST) from a sorted array

public class CreateBST {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9};
         Node root = null;
         for(int val:arr) {
             root =  insertNode(root, val);
         }
       
         Node node = createBST(arr, 0, arr.length-1);
         preorder(node);
    }
   
    static void preorder(Node node) {
        if(null!=node) {
            System.out.println(node.value);
            preorder(node.left);
            preorder(node.right);
        }
    }
   
    static Node insertNode(Node root, Integer value) {
        Node newNode = new Node(value);
        if (root == null) {
            return newNode;
        } else {
            if (value <= root.value) {
                root.left = insertNode(root.left, value);
            } else {
                root.right = insertNode(root.right, value);
            }
            return root;
        }

    }
    static class Node{
        Integer value;
        Node left;
        Node right;
        Node(Integer value){
            this.value = value;
            left = right = null;
        }
    }
   
    static Node createBST(int[] arr,int start,int end) {
        if(start>end) {
            return null;
        }
        int mid = (start+end)/2;
        Node node = new Node(arr[mid]);
        node.left = createBST(arr, start, mid-1);
        node.right = createBST(arr, mid+1, end);
        return node;
    }
   
    }

No comments:

Post a Comment

links for Data Structure

  1) 𝐁𝐞𝐜𝐨𝐦𝐞 𝐌𝐚𝐬𝐭𝐞𝐫 𝐢𝐧 𝐋𝐢𝐧𝐤𝐞𝐝 𝐋𝐢𝐬𝐭:  https://lnkd.in/gXQux4zj 2) 𝐀𝐥𝐥 𝐭𝐲𝐩𝐞𝐬 𝐨𝐟 𝐓𝐫𝐞𝐞 𝐓𝐫𝐚𝐯𝐞𝐫𝐬𝐚𝐥𝐬...