BinaryTree Data structure with methods

Question

I implemented a binary tree data structure. The data structure allows a binary tree to be built from a list (elements are inserted from left to right). How can I optimize insertElement? At the moment, it is recursive, so if tree is deep, it will run out of memory. How can I make it tail-recursive or even end-recursive?

public class Node {

    private int value;
    private boolean isLeaf;

    public Node (int value, boolean isLeaf){
        this.value = value;
        this.isLeaf = isLeaf;
    }

    public int getValue(){
        return value;
    }

    public void setLeaf(boolean value){
        this.isLeaf = value;
    }
    public boolean isLeaf(){
        return isLeaf;
    }

}



public class BinaryTree {

    Node root;
    BinaryTree left_child;
    BinaryTree right_child;

    public BinaryTree(){

    }
    public BinaryTree(Node root, BinaryTree left_child, BinaryTree right_child){
        this.root = root;
        this.left_child = left_child;
        this.right_child = right_child;
    }

    public BinaryTree insertElement(int element){
        if (root==null)
            return new BinaryTree(new Node(element, true), null, null);
        else {
            if (root.isLeaf()){
                root.setLeaf(false);
                if (element < root.getValue())
                    return new BinaryTree(root, new BinaryTree(new Node(element, true), null, null), null);
                else
                    return new BinaryTree(root, null, new BinaryTree(new Node(element, true), null, null));
            } else {
                if (element < root.getValue())
                    if (left_child!=null)
                        return new BinaryTree(root, left_child.insertElement(element), right_child);
                    else
                        return new BinaryTree(root, new BinaryTree(new Node(element, true), null, null), right_child);
                else
                    if (right_child!=null)
                        return new BinaryTree(root, left_child, right_child.insertElement(element));
                    else
                        return new BinaryTree(root, left_child, new BinaryTree(new Node(element, true), null, null));
            }
        }
    }

    public BinaryTree getLeftChild(){
        return left_child;
    }

    public BinaryTree getRightChild(){
        return right_child;
    }

    public void setLeftChild(BinaryTree tree){
        this.left_child = tree;
    }

    public void setRightChild(BinaryTree tree){
        this.right_child = tree;
    }

    public BinaryTree buildBinaryTree(int[] elements){
        if (elements.length==0)
            return null;
        else{
            BinaryTree tree = new BinaryTree(new Node(elements[0], true), left_child, right_child);
            for (int i=1;i<elements.length;i++){
                tree = tree.insertElement(elements[i]);
            }
            return tree;
        }
    }

    public void traversePreOrder(){
        if (root!=null)
            System.out.print(root.getValue() + " ");
        if (left_child!=null)
            left_child.traversePreOrder();
        if (right_child!=null)
            right_child.traversePreOrder();
    }

    public void traverseInOrder(){
        if (left_child!=null)
            left_child.traverseInOrder();
        if (root!=null)
            System.out.print(root.getValue() + " ");
        if (right_child!=null)
            right_child.traverseInOrder();
    }
    public void traversePostOrder(){
        if (left_child!=null)
            left_child.traversePostOrder();
        if (right_child!=null)
            right_child.traversePostOrder();
        if (root!=null)
            System.out.print(root.getValue() + " ");
    }

    public static void main(String[] args){
        int[] elements = new int[]{5,7,2,1,4,6,8};
        BinaryTree tree = new BinaryTree();
        tree = tree.buildBinaryTree(elements);
        tree.traversePreOrder();
        System.out.println();
        tree.traverseInOrder();
        System.out.println();
        tree.traversePostOrder();
        System.out.println();
    }

}

rbhawsar · Accepted Answer · 2012-10-01 03:50:45Z

1

if you think the tree would be too deep and run out of memory, better implement the logic with loop rather than using the recursion. temproot=root; while(inserted != true){

if(root==null)
    //add at the root.
else if(item<temproot->item )//it should go to left.
{
    if(temproot->left==null)
        //add your node here and inserted=true or put break; else just move pointer to   left.
 temproo=temproot->left; //take left address.

}
else if(it should go to right)
    //check the logic of above if clause.
}//end of while loop

and if you find that it should go to left and there is no child in left just add your node there. no need to put all the visited nodes in the system stack because anyway you are not using those nodes.

edited Oct 1, 2012 at 3:50

answered Oct 1, 2012 at 3:44

rbhawsar

8137 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Bob Over a year ago

how can you insert an element using loop? You need to navigate through the tree from top to down. Can you maybe post some code showing the control structure?

Bob Over a year ago

memory-wise, your solution would consume less. Is it always possible to write a loop version of recursive function? I came from a functional programming world, but Java seems to be lacking the power of functional programming languages as it builds a stack whenever there is a recursive call. Functional programming languages can handle recursive calls internally as loops.

swemon · Accepted Answer · 2012-10-01 03:43:06Z

0

In your coding, you create

Node class which contains only value and boolean variable isLeaf.

Whenever an element is created, you create a new binary tree based on the inserted element and append to the main tree.

The other way you can implement binary tree is

Node class contains its own value, left node and right node.

Inserting element still recursive but whenever you insert an element you do not need to create a new binary tree, just a new node like here

answered Oct 1, 2012 at 3:43

swemon

5,9664 gold badges36 silver badges55 bronze badges

6 Comments

Bob Over a year ago

If the node class contains the left node and right information, then it is already representing the binary tree fully. There is no need to have a binary tree class. Don't you think?

swemon Over a year ago

I don't understand what means "There is no need to have a binary tree class."

Bob Over a year ago

do you think it makes huge difference storagew-wise if I implement binary tree using only one class?

Bob Over a year ago

if I have a node class which contains all information I need to represent a binary tree, why would I define another class? that is what I meant with it.

swemon Over a year ago

@Bob have you seen my code sample roseindia.net/java/java-get-example/java-binary-tree-code.shtml. I mean a node class only contains all information about a node, not tree, that's means only his left child and right child. A binary tree is composed of many nodes.

|

Collectives™ on Stack Overflow

BinaryTree Data structure with methods

2 Answers 2

2 Comments

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related