Question

Problem 1:

Write a Java program for traversing a Binary Search Tree in following ways: (use any data structure, library functions) ---------- 20 points

i) Depth First Traversal: Inorder, LVR

ii) Depth First Traversal: Inorder, RVL

iii) Depth First Traversal: Preorder, VLR

iv) Depth First Traversal: Preorder, VRL

v) Depth First Traversal: Postorder, LRV

vi) Depth First Traversal: Postorder, RLV

No choice menu required.

Sample Input (taken from keyboard, single space separated nodes as found in a complete BFS: top-down, left to right traversal):

22 10 30 5 15 25 40 1 8

Sample Output (in console or in a file):

Depth First Traversal: Inorder, LVR -> 1 5 8 10 15 22 25 30 40

Depth First Traversal: Inorder, RVL -> 40 30 25 22 15 10 8 5 1

Depth First Traversal: Preorder, VLR -> 22 10 5 1 8 15 30 25 40

Depth First Traversal: Preorder, VRL -> 22 30 40 25 10 15 5 8 1

Depth First Traversal: Postorder, LRV -> 1 8 5 15 10 25 40 30 22

Depth First Traversal: Postorder, RLV -> 40 25 30 15 8 1 5 10 22

Answer 1

public class BinarySearchTree {

    class TreeNode {
        public int key;
        public TreeNode p;
        public TreeNode left;
        public TreeNode right;

        public TreeNode() {
            p = left = right = null;
        }

        public TreeNode(int k) {
            key = k;
            p = left = right = null;
        }
    }

    public TreeNode root;

    public BinarySearchTree() {
        root = null;
    }

    public void insert(int k) {
        TreeNode newNode = new TreeNode(k);
        
        if(root == null) {
            root = newNode;
        } else {
            TreeNode parent = root;
            while(true) {
                if(parent.key == k) {
                    return;
                }
                if(parent.key > k) {
                    if(parent.left == null) {
                        parent.left = newNode;
                        newNode.p = parent;
                        return;
                    } else {
                        parent = parent.left;
                    }
                } else {
                    if(parent.right == null) {
                        parent.right = newNode;
                        newNode.p = parent;
                        return;
                    } else {
                        parent = parent.right;
                    }
                }
            }
        }
    }

    private void inorderLVR(TreeNode t) {
        if(t != null) {
            inorderLVR(t.left);
            System.out.print(t.key + " ");
            inorderLVR(t.right);
        }
    }
    private void inorderRVL(TreeNode t) {
        if(t != null) {
            inorderRVL(t.right);
            System.out.print(t.key + " ");
            inorderRVL(t.left);
        }
    }


    private void preorderVLR(TreeNode t) {
        if(t != null) {
            System.out.print(t.key + " ");
            preorderVLR(t.left);
            preorderVLR(t.right);
        }
    }
    private void preorderVRL(TreeNode t) {
        if(t != null) {
            System.out.print(t.key + " ");
            preorderVRL(t.right);
            preorderVRL(t.left);
        }
    }


    private void postorderLRV(TreeNode t) {
        if(t != null) {
            postorderLRV(t.left);
            postorderLRV(t.right);
            System.out.print(t.key + " ");
        }
    }
    private void postorderRLV(TreeNode t) {
        if(t != null) {
            postorderRLV(t.right);
            postorderRLV(t.left);
            System.out.print(t.key + " ");
        }
    }
    

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] array = {22, 10, 30, 5, 15, 25, 40, 1, 8};
        BinarySearchTree bst = new BinarySearchTree();
        for (int i = 0; i < array.length; i++)
            bst.insert(array[i]);
        
        bst.printReport();
    }

    private void printReport() {
        System.out.print("Depth First Traversal: Inorder, LVR -> ");
        inorderLVR(root);
        System.out.println();
        System.out.print("Depth First Traversal: Inorder, RVL -> ");
        inorderRVL(root);
        System.out.println();
        System.out.print("Depth First Traversal: Preorder, VLR -> ");
        preorderVLR(root);
        System.out.println();
        System.out.print("Depth First Traversal: Preorder, VRL -> ");
        preorderVRL(root);
        System.out.println();
        System.out.print("Depth First Traversal: Postorder, LRV -> ");
        postorderLRV(root);
        System.out.println();
        System.out.print("Depth First Traversal: Postorder, RLV -> ");
        postorderRLV(root);
        System.out.println();
    }

}

**************************************************

Thanks for your question. We try our best to help you with detailed answers, But in any case, if you need any modification or have a query/issue with respect to above answer, Please ask that in the comment section. We will surely try to address your query ASAP and resolve the issue.

Please consider providing a thumbs up to this question if it helps you. by Doing that, You will help other students, who are facing similar issue.