(1) Implement a breadth first search non-recursively (2) Implement a depth first search non-recursively (3) Implement a breadth first search recursively (4) Implement a depth first search recursively

DfsAndBfs.java

import java.util.*;
 
class Node
{
    public Integer value;
    
    public int index;
    public int level;
    
    public Node(int index, int value, int level) 
    {
        this.value = value;
        this.index = index;
        this.level = level;
    }
}
 
class Main
{
    public static int leftChild(int index)
    {
        return index*2 + 1;
    }
    
    public static int rightChild(int index)
    {
        return index*2 + 2;
    }
    
    public static Vector<Node> convertToNodes(int tree[])
    {
        Vector<Node> vector = new Vector<Node>();
        
        int nodeCount = 0;
        int currentLevel = 1;
        int levelNodes = 1; // first level has one node
        
        for (int x = 0; x < tree.length; x++)
        {
            Node node = new Node(x, tree[x], currentLevel);
            vector.add(node);
            
            if ( ++nodeCount >= levelNodes )
            {
                nodeCount = 0;
                levelNodes = levelNodes * 2;
                currentLevel++;
            }
        }
        
        return vector;
    }
    
    public static Node depthFirstSearch(int tree[], int find)
    {
        Vector<Node> treeNodes = convertToNodes(tree);        
        Stack<Node> stack = new Stack<Node>();
        
        stack.push(treeNodes.get(0));
        
        while ( ! stack.isEmpty() )
        {
            Node n = stack.pop();
            
            System.out.println("Currently searching level = " + n.level + ", index = " + n.index);
            
            if ( n.value == null )
                continue;
            
            if ( n.value == find )
                return n;
                
            int leftIndex = leftChild(n.index);
            
            if ( leftIndex >= treeNodes.size() )
            {
                continue;
            }
                
            stack.push(treeNodes.get(rightChild(n.index)));
            stack.push(treeNodes.get(leftIndex));
        }
        
        // Value was not found
        return null;
    }
    
    public static Node breadthFirstSearch(int tree[], int find)
    {
        Vector<Node> treeNodes = convertToNodes(tree);
        Queue<Node> q = new LinkedList<Node>();
        
        q.add(treeNodes.get(0));
        
        while ( ! q.isEmpty() )
        {
            Node n = q.remove();
            System.out.println("Currently searching level = " + n.level + ", index = " + n.index);
            
            if ( n.value == null )
                continue;
            
            if ( n.value == find )
                return n;
                
            int leftIndex = leftChild(n.index);
            
            if ( leftIndex >= treeNodes.size() )
                continue;
                
            q.add(treeNodes.get(leftIndex));
            q.add(treeNodes.get(rightChild(n.index)));
        }
        
        // Value was not found
        return null;
    }
    
    public static Node breadthFirstSearch_Recursive(Vector<Node> treeNodes, int find, Queue<Node> toSearch)
    {
        Node node = toSearch.poll();
        
        if ( node == null )
            return null;
 
        int leftIndex = leftChild(node.index);
        if ( leftIndex < treeNodes.size() )
            toSearch.add(treeNodes.get(leftIndex));
        
        int rightIndex = rightChild(node.index);
        if ( rightIndex < treeNodes.size() )
            toSearch.add(treeNodes.get(rightIndex));
                   
        System.out.println("Currently searching level = " + node.level + ", index = " + node.index);
        
        if ( node.value == null )
            return null;
        
        if ( node.value == find )
            return node;
            
        return breadthFirstSearch_Recursive(treeNodes, find, toSearch);
    }
 
    public static Node breadthFirstSearch_Recursive(int tree[], int find)
    {
        Vector<Node> treeNodes = convertToNodes(tree);
        
        Queue<Node> toSearch = new LinkedList<Node>();
        toSearch.add(treeNodes.get(0));
        
        return breadthFirstSearch_Recursive(treeNodes, find, toSearch);
    }
    
    public static Node depthFirstSearch_Recursive(Vector<Node> treeNodes, int index, int find)
    {
        Node node = treeNodes.get(index);
        System.out.println("Currently searching level = " + node.level + ", index = " + node.index);
        
        if ( node.value == null )
            return null;
        
        if ( node.value == find )
            return node;
            
        int leftIndex = leftChild(node.index);
        if ( leftIndex >= treeNodes.size() )
            return null;
 
        Node left = depthFirstSearch_Recursive(treeNodes, leftIndex, find);
        if ( left != null )
        {
            return left;
        }
        
        int rightIndex = rightChild(node.index);
        if ( rightIndex >= treeNodes.size() )
            return null;
        
        Node right = depthFirstSearch_Recursive(treeNodes, rightIndex, find);
        if ( right != null )
        {
            return right;
        }
        
        return null;
    }
    
    public static Node depthFirstSearch_Recursive(int tree[], int find)
    {
        Vector<Node> treeNodes = convertToNodes(tree);
        return depthFirstSearch_Recursive(treeNodes, 0, find);
    }
 
    public static void main(String args[])
    {
        {
            Node found = breadthFirstSearch(new int[] {1, 2, 3, 4, 5, 6, 7}, 7);
            System.out.println("Found = " + found.value + ", index = " + found.index + ", level = " + found.level);
        }
        {
            Node found = depthFirstSearch(new int[] {1, 2, 3, 4, 5, 6, 7}, 7);        
            System.out.println("Found = " + found.value + ", index = " + found.index + ", level = " + found.level);
        }
        {
            Node found = depthFirstSearch_Recursive(new int[] {1, 2, 3, 4, 5, 6, 7}, 7);        
            System.out.println("Found = " + found.value + ", index = " + found.index + ", level = " + found.level);
        }
        {
            Node found = breadthFirstSearch_Recursive(new int[] {1, 2, 3, 4, 5, 6, 7}, 7);        
            System.out.println("Found = " + found.value + ", index = " + found.index + ", level = " + found.level);
        }
    }
}