How to construct a BST with a given pre-order array?

Code is below:

    // build the tree
    private TreeNode build_tree( String[] node, int min, int max ){

        // invalid corner case
        if( idx >= node.length ){
            return null;
        }

        TreeNode root = null;

        // valid value
        if( Integer.valueOf(node[idx]) > min && Integer.valueOf(node[idx]) < max ){

            // build the root
            root = new TreeNode( Integer.valueOf( node[idx]) );
            //System.out.println("Now insert: " + node[idx] );
            idx++;
            // 
            if( idx < node.length ){
                root.left = build_tree( node, min, root.val );
                root.right = build_tree( node, root.val, max );
            }

        }

        return root;
    }

The main idea is to set the range, using min and max, to get the valid node from the given array. I apply this algorithm in this problem.

Leave a Reply