Write a Java method for a given array, and a tolerance, generate all possible bi

Question

Write a Java method for a given array, and a tolerance, generate all possible binary trees with the same inorder traversal, so that at any node, its left and right subtree heights differ by no more than the tolerance. Output all the preorder traversals. Example: {1,2,3,4} and tolerance 1 will produce, {2,1,3,4}, {2,1,4,3}, {3,1,2,4}, {3,2,1,4} Write a Java method for a given array, and a tolerance, generate all possible binary trees with the same inorder traversal, so that at any node, its left and right subtree heights differ by no more than the tolerance. Output all the preorder traversals. Example: {1,2,3,4} and tolerance 1 will produce, {2,1,3,4}, {2,1,4,3}, {3,1,2,4}, {3,2,1,4}

Explanation / Answer

import java.util.Vector;
/* left and right child of current node and key value*/
class Node {
    int data;
    Node left, right;

    public Node(int value) {
        data = value;
        left = null;
        right = null;
    }
}
/* Print Level Order Traversal */
class BinaryTree {

    Node root;

    // preorder traversal of BST
    void preOrder(Node node) {
        if (node != null) {
            System.out.print(node.data + " "    );
            preOrder(node.left);
            preOrder(node.right);
        }
    }

/******************************************************************************************************
*   Construct all possible trees with given inorder traversal stored in an array from arr[start]
*   to arr[end]. This function returns a
*    vector of trees
*******************************************************************************************************/
    Vector<Node> getTrees(int arr[], int start, int end) {

        // List to store all possible Trees
        Vector<Node> Trees= new Vector<Node>();

        if (start > end) {
            Trees.add(null);
            return Trees;
        }

        /* Iterating for constructing left and right subtree recursively */
        for (int i = start; i <= end; i++) {
          
            Vector<Node> ltrees = getTrees(arr, start, i - 1);
           
          
            Vector<Node> rtrees = getTrees(arr, i + 1, end);

            /* connecting to ith root with left and right subtrees */
            for (int j = 0; j < ltrees.size(); j++) {
                for (int k = 0; k < rtrees.size(); k++) {

                     Node node = new Node(arr[i]);
                     // Connecting left subtree
                    node.left = ltrees.get(j);
                    // Connecting right subtree
                    node.right = rtrees.get(k);
                   
                    Trees.add(node);
                }
            }
        }
        return Trees;
    }

    public static void main(String args[]) {
        int in[] = {1, 2, 3, 4};
        int n = in.length;
        BinaryTree Tree = new BinaryTree();
        Vector<Node> Trees = Tree.getTrees(in, 0, n - 1);
        System.out.println("Preorder traversal of different "+
                           " binary trees are:");
        for (int i = 0; i < Trees.size(); i++) {
            Tree.preOrder(Trees.get(i));
            System.out.println("");
        }
    }
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.