DFS and BFS

In this section, we will implement naive DFS and BFS algorithm.

We first define the tree and its initialisation function.

class SSETreeDFSBFS{

    private SSETreeInternal root;

    private class SSETreeInternal {
        int val;
        private SSETreeInternal left;
        private SSETreeInternal right;

        public SSETreeInternal(int val) {
            this.val = val;
            left = null;
            right = null;
        }
    }

    public SSETreeDFSBFS(int val){
        SSETreeInternal sseTreeInternal = new SSETreeInternal(val);
        root = sseTreeInternal;
    }

    public void add(int val){
        add(root, val);
    }

    private SSETreeInternal add (SSETreeInternal root, int val){
        if (root == null){
            return new SSETreeInternal(val);
        }else {
            if (val > root.val){
                root.right = add(root.right, val);
            }else{
                root.left = add(root.left, val);
            }
            return root;
        }
    }
}

Next we will define DFS algorithm which goes to most left of tree first.

    public void printDFS(){
        DFSprint(root);
    }
    private void DFSprint(SSETreeInternal root){
        if (root != null) {
            DFSprint(root.left);
            System.out.print(root.val + " ");
            DFSprint(root.right);
        }
    }

Next we will define BFS algorithm which goes from the root and go down one level down each time.

     public void printBFS(){
        BFSprint(root);
    }

    private void BFSprint(SSETreeInternal root){
        Queue<SSETreeInternal> q = new LinkedList<>();
        q.add(root);

        while(!q.isEmpty()){
            SSETreeInternal currentNode = q.poll();
            System.out.print(currentNode.val + " ");

            if (currentNode.left != null){
                q.add(currentNode.left);
            }
            if (currentNode.right != null){
                q.add(currentNode.right);
            }
        }

    }

You can try to run the code here:

Run on jdoodle