Create a binary tree (but not BST)

1
votes

When I create a BST, during insertion of nodes I check whether the value of the new node is less than left child or greater than right child. And I traverse my way down till I find the correct position to insert the node. Now suppose I have a binary tree and I want to create a tree how would I do that? Do i need to use BFS algorithm to do that?

Thank you

2
algorithmdata-structurestreebinary-tree

2 Answers

3
votes

That is not how the insertion should work in a BST, the new value should be compared to the current node not to its children, if it is less than the value of the current node traverse left if there is a left node compare the value to it, and if no left node exists insert the value there. The same goes for the right side but if the comparison result was greater than the current node (there is no repeated values in a BST).

Your question is on how to create a binary tree not a BST, if you want a simple Binary tree that constructs a complete binary tree then just insert the nodes layer by layer from left to right. Certainly BFS works layer by layer but it is a search algorithm and you don't need to search through the tree since you are constructing it from scratch.

Edit: if you want a simpler version of binary tree construction, just insert 2 nodes all the way down in one branch without backtracking, still a binary tree even if you insert 1 node too.

Enother Edit: Every BST is a binary tree and every binary tree is a tree and this argument cannot be inverted (e.g. not every BT is a BST ...etc). So if you have a BT it is already a tree.

Regards,

1
votes

In here, I'm making a Weight-based Binary Tree which is good for BFS, since it keeps the tree balanced ..

I'd implement it like this in Java:

class BT_Node
{
    public int value;
    public int depth;
    public long weight;
    public BT_Node left, right;

    public BT_Node (int value, int depth)
    {
        this.depth = depth;
        this.value = value;
        this.weight = 0;
        this.left = this.right = null;
    }
}

class BT
{
    private BT_Node root;

    public long size ()
    {
        return (root!=null ? root.weight : 0);
    }

    public long size (BT_Node node)
    {
        return (node!=null ? node.weight : 0);
    }

    public void insert (int value)
    {
        int depth = 0;
        BT_Node parent = root;

        if (root == null)
        {
            root = new BT_Node (value, 0);
        }
        else
        {
            root.weight++;

            while (parent.left!=null && parent.right!=null)
            {
                if (parent.left.weight <= parent.right.weight)
                    parent=parent.left;
                else
                    parent=parent.right;

                parent.weight++;
            }

            if (parent.left == null)
                parent.left = new BT_Node (value, parent.depth+1);
            else
                parent.right = new BT_Node (value, parent.depth+1);
        }
    }
}