Question

Write a binary search tree with 10 nodes in Java, each node will have 3 attributes (data, x, y). The binary tree need to have function "add()" to add new node into the tree. After added all 10 nodes, it will be sorted and turn into a balanced binary search tree.

Answer 1

NOTE:If you have any doubts or confusion please feel free to ask in the comments but do not give negative rating to the question as it affects my answering rights......i will try my best to help you understand the question

Hope you know what a preorder traversal is and you can interpret a tree based on the preorder traversal...it will help you understand the working of the recursion to build a balanced binary tree.Also all the functions are recursion based make sure you understand them

The code works perfectly well...you can just copy paste the code to any online editor and see it work

import java.util.*; 
import java.io.*;

//x refers to left child and y refers to right child of a node
class Node //this class represents a single node in the tree
{ 
        int data; 
        Node x, y; 

        public Node(int data) 
        { 
                this.data = data; 
                x = y = null; 
        } 
} 

public class BinaryTree 
{ 
        Node root; 

        /* This function traverse the skewed binary tree and 
        stores its nodes pointers in vector nodes[] */
        void inorder(Node root, Vector<Node> nodes) 
        { 
                // Base case 
                if (root == null) 
                        return; 

                // Store nodes in Inorder (which is sorted 
                // order for BST) 
                inorder(root.x, nodes); 
                nodes.add(root); 
                inorder(root.y, nodes); 
        } 
    Node balancedTree(Vector<Node> nodes, int start, int end)  
    { 
        //the idea is to get the middle index and divide the vector based on this index
        
            // base case 
            if (start > end) 
                return null; 
      
            /* Get the middle element and make it root */
            int mid = (start + end) / 2; 
            Node node = nodes.get(mid); 
      
            /* Using index in Inorder traversal, construct 
               left and right subtress */
            node.x = balancedTree(nodes, start, mid - 1); 
            node.y = balancedTree(nodes, mid + 1, end); 
      
            return node; 
        } 
      
    // This functions converts an unbalanced BST to 
    // a balanced BST 
    Node buildTree(Node root)  
    { 
        //The first and the foremost requirement is that we need a sorted array of given binary tree
        //so the most simple approach is to do the inorder traversal of the tree and store the visited node in the same
        //order in a vector ,Hence we called the inorder func and stored the sorted nodes in a vector named nodes
        Vector<Node> nodes = new Vector<Node>(); 
        inorder(root, nodes); 
  
        // Constucts BST from nodes[] 
        int n = nodes.size(); 
        return balancedTree(nodes, 0, n - 1); //now recursively call the utilityfunction which is balancedTree here
    } 

    //the idea of adding a node is simple 
    //if the tree is empty make the data as root node
    //if the new node is less than the current node than move to the left child which is x here
    //if the new node is more than the curent node than move to the right child which is y here
        Node add(Node root,int n_data) 
        { 
            Node tmp=root;
            if(root == null){
                root=new Node(n_data);
                return root;
            }
            if (n_data < root.data) 
            root.x = add(root.x, n_data); 
        else if (n_data > root.data) 
            root.y = add(root.y, n_data); 
  
        return root; 
        } 

    //this function gives the preorder traversal of a tree
    //this is here to confirm if out program worked or not
        void preOrder(Node node) 
        { 
                if (node == null) 
                        return; 
                System.out.print(node.data + " "); 
                preOrder(node.x); 
                preOrder(node.y); 
        } 

        public static void main(String[] args) 
        { 
            Scanner sc=new Scanner(System.in);
                BinaryTree tree = new BinaryTree(); 
                System.out.println("Enter the nodes :"); 
            for(int i=0;i<10;i++){
             int tmp;
             tmp=sc.nextInt();
             tree.root= tree.add(tree.root,tmp);
            }
            System.out.println("Preorder traversal of BST is :"); 
            tree.preOrder(tree.root); 
            tree.root = tree.buildTree(tree.root); 
                System.out.println("\nPreorder traversal of balanced BST is :"); 
                tree.preOrder(tree.root); 
        } 
} 

Output:-->