Binary Tree Traversal not showing full list

Question

so currently I’m trying to follow a tutorial from FreeCodeCamp on implementing a Binary tree, but I’m having trouble with adding to and traversing through my tree.

For some reason, it seems that I’m able to add nodes to my tree, but when I try to traverse through my tree via iterative preorder traversal, it only picks up my root node. Its as if my nodes aren’t pointing to each other.

I have a feeling that the problem either lies with my add method or my traversal method, both of which are below. Any help would be greatly appreciated.

Add method:

public boolean add(T thing) 
    {
        if(contains(thing)) 
        {
            return false;
        } else {
            root = add(root,thing); 
            count++;
            return true;
            
        }
        
    }
    
    
    private Node add(Node node,T thing) 
    {
        if(node == null) 
        {
            node = new Node(thing,null,null); 
        } else
        {
            if(thing.compareTo(node.value) <0) 
            {
                if(node.left == null)
                {
                    node.left = node = new Node(thing,null,null);
                } else{
                node.left =add(node.left,thing);
                }
            }
            else 
            {
                if(node.right == null)
                {
                    node.right = node = new Node(thing,null,null);
                }else {
                node.right = add(node.right,thing);
                }
            }
            
        }
        
        return node;
    }

Traversal:

public void traverse()
   {
       preorder(root);
   }
   
   private void preorder(Node node)
   { int iteration=0;
       java.util.Stack<Node> stack = new java.util.Stack<Node>();
       System.out.println( "root is: " +node.value);
       stack.push(node);
       
       while(stack.empty() == false)
       {
            Node current = stack.pop();
            System.out.println("in preorder: "+current.value);
            
            if(current.right != null)
            {
                stack.push(current.right);
            }
            if(current.left != null)
            {
                stack.push(current.left);
            }
            iteration++;
            
       }
       System.out.println("iteration: "+iteration);
       
       
   }

It would help if you would provide a minimal reproducible example that also includes the code that populates the tree with the test data that demonstrates the problem. — WJS
node.right = node = new Node(...) - that seems strange to me. Are you sure you really sure this does what you want it to do? Please don't do that, it is very confusing to read - split it in two lines. — Hulk
Also, it seems like add always returns the new leaf node, but you then assign that return value to root = add(root,thing); — Hulk

prachi julka prachi julka · Accepted Answer · 2020-08-27T14:42:05

You are not traversing your tree while adding in the tree. Check my tree insert method to get the idea:-

void insert(Node temp,int value) {
            if(temp==null){
                temp=new Node(value,null,null);
                this.root=temp;
            }
            else{
            Queue<Node> q = new LinkedList<>();
            q.add(temp);

            while (!q.isEmpty()) {
                temp = q.peek();
                q.remove();

                if (temp.left == null) {
                    temp.left = new Node(value, null, null);
                    break;
                } else
                    q.add(temp.left);

                if (temp.right == null) {
                    temp.right =new Node(value, null, null);
                    break;
                } else
                    q.add(temp.right);
            }
        }
    }

Binary Tree Traversal not showing full list

1 Answers