7

I need to create an unsorted binary tree (one requirement is that it is unsorted) that holds a String as its value. My class outline looks like this:

public class Node {

 private String desc;
 private Node leftNode = null;
 private Node rightNode = null;

 public Node(String desc) {
  this.desc = desc;
 }

 public String getDesc() {
  return desc;
 }

 public Node getLeftNode() {
  return leftNode;
 }

 public Node getRightNode() {
  return rightNode;
 }
}

Eventually I want to be able to replace any node that matches a String description with a new node that has a new description (including duplicates with the old description).

So my question is, what is the best way to handle the insertion of Nodes when creating an unsorted binary tree?

I thought of two ways. The first would be to just have two methods, setLeftNode(Node root, String desc) and setRightNode(Node root, String desc) that someone could call with a Node of their choice as the root. If there already is a left/right Node, then it would just advance down until it hit a node that didn't have a left Node. But this could introduce problems by producing super large heights.

The second way I thought of would be to have a dedicated root Node, in this case the first Node created, and then to just build new Nodes in order.

So what is the best way to create an unsorted binary tree?

Improve this question
3
  • 2
    The most efficient way of creating an unsorted binary tree from a list of items is just to take the list of items and consider element 0 the root, element 1 and 2 the left and right nodes of element 0, etc. This gives you a perfectly balanced tree with zero work. But what's the point of this tree in the first place? Commented May 10, 2015 at 1:16
  • @Alex as per my understanding a regular Binary Tree is always unsorted. Commented May 10, 2015 at 1:28
  • @Alex if you are looking for a Binary Search Tree then obviously it has its own well defined ordering scheme. For Binary Tree there is no best way as such it all depends on how you want to do it, based on your requirements. Commented May 10, 2015 at 2:00

5 Answers 5

Reset to default
3 
public class BinaryTree{
    private BinaryTree right;
    private BinaryTree left;
    private String data;        

    public BinaryTree(String s){
        data = s;
        right = null;
        left = null;           
    }

    public void setLeft (BinaryTree l){ left  = l; }
    public void setRight(BinaryTree r){ right = r; }        
}

Your question suggests that the tree should be balanced and so on insertion of an element, you should recursively check number of nodes at each side of the tree:

public int checkTree(){
    if(left == null && right == null){
        return 1;
    }else if(left == null){
        return 1 + right.checkTree();
    }else if(right == null){
        return 1 + left.checkTree();
    }else{
        return 1 + left.checkTree() + right.checkTree();
    }
}

public void insert(BinaryTree bt){
    if(left == null){
        setLeft(bt);
    }else if(right == null){
        setRight(bt);
    }else{
        if(left.checkTree() <= right.checkTree()){
            left.insert(bt);
        }else{
            right.insert(bt);
        }
    }
}






EDITED:

public class BinaryTree {
    private BinaryTree right;
    private BinaryTree left;
    private String data;
    private int weight;

    public BinaryTree(String s){
        data = s;
        right = null;
        left = null; 
        weight = 1;
    }    

    public void setLeft (BinaryTree l){ 
        left  = l;
        weight++;
    }

    public void setRight(BinaryTree r){
        right = r;
        weight++;
    } 

    public int getWeight(){ return weight; }

    public void insert(BinaryTree bt){
        if(left == null){
            setLeft(bt);
        }else if(right == null){
            setRight(bt);
        }else{
            if(left.getWeight() <= right.getWeight()){
                left.insert(bt);
                weight++;
            }else{
                right.insert(bt);
                weight++;
            }
        }
    }    
}
Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

What exactly is the need of (left == null && right == null) || left == null) in insertion? And what is checkTree() actually trying to do?
The need of (left == null && right == null) || left == null) is to check whether subtrees are null, because we can't call insert() on null value - it has to be a tree. checkTree() recursively counts number of nodes and by comparing values returned from left subtree and right subtree, we can always select the right branch to call insert() on. insert() is - as you can see - also recursive and it will go into a branch until it finds the source of imbalance. This way our tree is always balanced.
Don't you think if(left == null) setLeft(bt); will also work? Why need to check both nodes? For balancing your tree IMO this recursive solution is too much of overhead. Imagine you want to insert 10000 nodes.
if(left == null) setLeft(bt); - yes, you're right. About the overhead, balancing is always expensive but obviously there are other ways to do that. Insertion speed could be improved by introducing additional attribute, which would hold number of nodes in subtrees and be updated with each insertion. Gain speed by sacrificing some memory. On the other hand, some memory would also be freed, cause we wouldn't need checkTree() method anymore :)
Trust me, recursive methods are mostly not the preferred choice in a real world project :)
|
1

by definition a binary tree has its lowest elements on the left, and the highest on the right. But if you really want that all messed up (sorted) you can call a rand function that results in 0 or 1, and if 0 then go to left, if 1 go to right, randomly. That will result in an unsorted tree

Improve this answer

7 Comments

A Binary Search Tree is an ordered binary tree, no? Meaning Binary Tree elements are not always ordered with the smallest elements on the left/largest elements on the right.
a binary tree has its lowest elements on the left, and the highest on the right Can you please elaborate?
IMO you are wrong. Please refrain from posting wrong answers.
"A binary search tree is a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree additionally satisfies the binary search tree property, which states that the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in right sub-tree.[1] (The leaves (final nodes) of the tree contain no key and have no structure to distinguish them from one another." , from Wikipedia
A Binary Tree is not exactly same as Binary Search Tree and OP asked for Binary Tree.
|
1

Eventually I want to be able to replace any node that matches a String description with a new node that has a new description (including duplicates with the old description).

For that you will have to search your entire tree as:

private Node searchBasedOnValue(String desc, Node currentNode)
{  
    Node result = null
    if (currentNode == null)
        return null;
    if (currentNode.getDesc().equals(desc)) 
        return currentNode ;
    if (currentNode.getLeftNode() != null)
        result = searchBasedOnValue(desc,currentNode.getLeftNode());
    if (result == null)
        result = searchBasedOnValue(desc,currentNode.getRightNode());
    return result;
}

IMO, a regular Binary Tree is never sorted the one which is sorted is called Binary Search Tree. For insertion you need to handle the way you want it. May be you can insert nodes alternatively to left and right child of your tree so that it is balanced to some extent. That is up to you how you take care of that.

I have not seen much practical usage for regular Binary Tree as most of the times we use Binary Search Tree which have better performance (lg(n)) in terms of insertion, deletion and lookup.

Improve this answer

Comments

0

If it is unsorted, why build a binary tree at all? You can't search it without doing a full scan, so you might as well put everything in an array, as accessing any element will be O(n), due to the inability to search.

Improve this answer

Comments

0

This is the fastest way to build an unsorted binary tree without any constraints on its shape:

First you need a constructor like this:

   public Node(String desc, Node left, Node right) {
       this.desc = desc;
       this.left = left;
       this.right = right;
   }

Then build the tree like this:

   Node root = null;
   for (String input: ...) {
      root = new Node(input, root, null);
   }

Obviously, this gives you an unbalanced, unsorted tree for which searching entails looking at all of the nodes. However, if the tree is unsorted, then the fact that the tree is unbalanced makes no difference.

In general, searching an unsorted tree has the same complexity as searching a list, and the code is more complex.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.