how do you remove a node from a binary tree?

[Dmitri Makovetskiy]

   

public class BTree {
    public static void main(String[] args) {
    Btree2 tree=new Btree2();
    tree.add(10);
    tree.add(20);
    tree.add(50);
    tree.add(100);
    tree.add(12);
    tree.add(1);
    tree.print();
    tree.remove(50);
    }

    
    }

class Btree2{
    private Node head;
    public void add(int number){ // builds a binary tree
        Node node=new Node(number);
        if(head==null){
            head=node;
        }
        Node current=head;
        while(true){
            if(number<current.info){
                if(current.left==null){
                    current.left=node;
                    return;
                }
                else{
                    current=current.left;
                }
            }
            if(number>current.info){
                if(current.right==null){
                    current.right=node;
                    return;
                }
                else{
                    current=current.right;
                }
            }
            
        }
    
    }
    
    void print(){
        print(head);
    }
    public void print(Node unit){ // prints the tree
        if(unit==null)
            return;
        print(unit.left);
        System.out.println(unit.info);
        print(unit.right);
        
    }
    
    public void remove(int number){// removes the head
        Node left = null;
        Node right = null;
        
        if(head.info==number){
            left=head.left;
            right=head.right;
        }
            
        if(left==null && right==null){
            head=null;
        }
        if(left!=null){
            head=left;
            addUnit(right);// why do i need the addUnit?
        }
        else{
            head=right;
        }
        remove(head,number);
        
    }
    
    
    
    
    
    private void remove(Node unit, int number) { // removes the corresponding nodes and misplacing them under the correct node.
    Node right = null;
    Node left = null;
      if(unit==null)
      return;
      remove(unit.left, number); // recursion, checking the left nodes.
      if(unit.left!=null)
      if(unit.left.info==number){
          right=unit.left.left; // moving the nodes to the left side.
          unit.left=unit.left.right;
          addUnit(right); // why addUnit, right only and not left too?
      }
      if(unit.right!=null)
        if(unit.right.info==number){
          left=unit.right.left;        // moving the node chain to the right node. 
          unit.right=unit.right.right;
          addUnit(left); // why addUnit , left only and not right node too??
      }
      remove(unit.right, number); // recursion checking the right side.
        
    }

    
    
    private void addUnit(Node unit){ // builds a binary tree.
        Node current=head;
        if(unit==null)
            return;
        while (true) {
            if(unit.info<current.info){
                if(current.left==null){
                    current.left=unit;
                    return;
                }
                else
                    current=current.left;
            }
            else{
                if(current.right==null){
                    current.right=unit;
                    return;
                }
                else
                    current=current.right;
            }
        }
    }
}


class Node{
    int info;
    Node right;
    Node left;
    
    Node(int info){
        this.info=info;
    }
} 

did i do it right. first, make a function to check the head , whether to remove it, and then call for a function to remove nodes from the body, and transfer the chain underneath to another node..

one thing that i didnt understand is why do you need addUnit(right), addUnit(left) .. in the order described in the remove functions?

[David Newton]

Why would you add a node to both the left and right nodes?

And the usual advice: write out the algorithm, draw a picture, whatever helps you understand. Run through a few cases:

- No nodes
- A single node
- A few nodes

That should be enough to make the algorithm understandable.

[David Newton]

(I have deleted your post in which you question my usefulness so that you will not be banned from the site. Please refrain from insulting the staff and being inflammatory, and recognize that not only *am* I helping you, I am the *only* one helping you. Unfortunately, you refuse to help *yourself*, which is pretty much one of the only rules of JavaRanch, along with BeNice. If you fail to BeNice one more time, the ban hammer will be wielded.)