How do I create a unbalanced binary search tree

Question

public class Tree { Node root;

// Tree Node 
static class Node { 
    int data; 
    Node left, right; 
    Node(int data) 
    { 
        this.data = data; 
        this.left = null; 
        this.right = null; 
    } 
    @Override public String toString() { 
     return String.valueOf(data); 
     }
} 

// Function to insert nodes in level order 
public Node insertLevelOrder(int[] arr, Node root, 
                                            int i) 
{ 
    // Base case for recursion 
    if (i < arr.length) { 
        Node temp = new Node(arr[i]); 
        root = temp; 

        // insert left child 
        root.left = insertLevelOrder(arr, root.left, 
                                         i + 1); 

        // insert right child 
        //root.right = insertLevelOrder(arr, root.right, 
                                          // 2 * i + 2); 

        //System.out.println(root);  
    } 
    return root; 
} 

// Function to print tree nodes in InOrder fashion 
public void inOrder(Node root) 
{ 
    if (root != null) { 
        inOrder(root.left); 
        System.out.print(root.left + " "); 
        //inOrder(root.right); 
    } 
} 

// Driver program to test above function 
public static void main(String args[]) 
{ 
    Tree t2 = new Tree(); 
    int arr[] = {9,5,0,-3,-10}; 
    t2.root = t2.insertLevelOrder(arr, t2.root, 0); 
    t2.inOrder(t2.root); 
} 
}

I don know if those nodes are been inserted or not, but the output return me right thing. I would like insert nodes only to the left child, can I eliminate that code? root.right = insertLevelOrder(arr, root.right, 2 * i + 2);

And also why this loop doesn't have a sign that "i++", how does int i increase automatically?

Unrelated: read about Java naming conventions. And stop using one character names that mean nothing. "C" is a really bad name for a variable or parameter! — GhostCat
Frankly your code seems a bit confused both in design, code and naming conventions (as mentioned). I have not followed your logic. I have dared post an answer nevertheless. — Ole V.V.
@greybeard I'm using “replit" which can allow us coding on the webpage(like google colab), It's not eclipse and it looks like we can't change the class name "Main" which is automatically been created when you create a new project. — TIGUZI
If you have a different question now, I suggest rolling back to revision 5 and asking a new question. — greybeard

Jean-Baptiste Yunès Jean-Baptiste Yunès · Accepted Answer · 2019-12-14T09:59:52

There is a lot of missing things. I will not solve everything for you (that is not the purpose of SO), but will give you hints.

First, you need to have something to build a tree (set left and right node of a node) :

public class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) {
         val=x;
     }
     TreeNode(int v,TreeNode l,TreeNode r) {
         this(x);
         left = l;
         right = l;
     }   
     @Override public String toString() {
         return "(" + (left==null?"*":left) + "," + val + "," + (right==null?"*":right) + ")";
     }
}

Thus you can then create (and print) a tree like this (for example) :

TreeNode n1 = new TreeNode(1);
TreeNode n3 = new TreeNode(3);
TreeNode n2 = new TreeNode(2,n1,n3);
TreeNode n4 = new TreeNode(4,n3,null);
System.out.println(n4);

Second, write a function to get a node from a given value (left as an exercise, think about it, hint: recursive binary search).

Third you need a function to insert a node (left as an exercise to you), so you need:

to find the node that point to the node that should be inserted (if you solved the second point that should be easy)
connect the node to existing ones (easy)

How do I create a unbalanced binary search tree

2 Answers