Construct Binary Search Tree from Pre Order Traversal

It is Thanksgiving Week 2020 and we do not have a winner in the 2020 Presidential Elections yet. The amount of fraud in this year’s elections has been unprecedented. My comment has nothing to do with politics. It is just based on common sense for individuals 12 years of age and older. I have friends and relatives living in different parts of the world. Their confidence and respect in the USA is almost (never generalize) gone.

On multiple occasions and referring to different topics, I have mentioned in this blog a technique used when people want to understand the positions of each other. First both argue on behalf of their own positions. Then, and this is the key of the technique, they switch positions and argue in favor of the opposite position. It is amazing what you can learn about different ideas when you use this technique. The reason for this tends to be based on facts and logic.

Over the weekend I selected LeetCode problem 1008 Construct Binary Search Tree from Preorder Traversal.

A binary search tree is a binary tree in which for each node, the values on the left sub tree are smaller than on the node, and the values on the right sub tree are larger. A pre order binary tree traversal implies first visiting the node, then the left sub tree and finally the right sub tree. We have performed different binary tree traversals for different posts in this blog.

Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, 
any descendant of node.left has a value < node.val, and any descendant of node.right 
has a value > node.val.

Also recall that a preorder traversal displays the 
value of the node first, 
then traverses node.left, 
then traverses node.right.)

It's guaranteed that for the given test cases there is always possible to find a 
binary search tree with the given requirements.

Constraints:

o 1 <= preorder.length <= 100
o 1 <= preorder[i] <= 10^8
o The values of preorder are distinct.

The description is quite simple. We are given the data for the BST in a pre order traversal form, and we are asked to build the associated BST. Typically we go the other way. We are given a BST and we are required to display the values of the nodes when we perform different tree traversals.

The rest of the information should make one think about the structure of a BST and how nodes are related to each other.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        
    }
}

If you like to solve LeetCode problems, the TreeNode data structure should be quite familiar. It is a simple representation of a node used in a binary tree. Not sure if we are allowed to modify it in order to solve this problem, but in general, unless explicitly stated in the requirements, DO NOT ALTER the classes or data structures.

Our solution requires for us to implement the bstFromPreorder() function which is given an array with the values for the BST in preorder traversal order.

2,1,3
main <<< preorder: [2, 1, 3]
main <<<  inOrder: 1 2 3  


8,5,1,7,10,12
main <<< preorder: [8, 5, 1, 7, 10, 12]
main <<<  inOrder: 1 5 7 8 10 12

We have two test examples. The second was provided by LeetCode. You can read all about it in the LeetCode web site. The first test case, which I edited a few times, represents the simplest binary tree with a root and two children. I used it to help me figure out and test the approach. Initially you can have global variables and then you can switch them to arguments.

/**
 * Definition for a binary tree node.
 */
class TreeNode {

    // **** class members ****
    public int val;
    public TreeNode left;
    public TreeNode right;

    // **** constructor(s) ****
    public TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    // **** ****
    @Override
    public String toString() {
        return "" + this.val;
    }
}

Since I like to solve problems using my own environment and tools, I have to build a test scaffolding. For this reason I had to implement the TreeNode class. If you solve the problem on-line you do not have to implement this class.

The only thing I did to the TreeNode class is to add the toString() method. It is not used or required to solve the problem.

I will solve the problem using the Java programming language, on a Windows 10 platform and the VSCode IDE. The particular machine has a Dell P4317Q 42.5″ 16:9 4K IPS Monitor which is quite nice to work with. My other machines have a dedicated monitor or two monitors attached via KVM switches. They are all 23” flat screens.

    /**
     * Test scaffolding.
     * 
     * !!! This method is not part of the solution !!!
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {

        // **** open buffered reader ****
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        
        // **** ****
        String[] strs = reader.readLine().split(",");

        // **** close buffered reader ****
        reader.close();

        // **** allocate and populate array ****
        int[] preorder = new int[strs.length];
        for (int i = 0; i < strs.length; i++) {
            preorder[i] = Integer.parseInt(strs[i]);
        }

        // ???? ????
        System.out.println("main <<< preorder: " + Arrays.toString(preorder));
        
        // **** generate the BST from the specified array ****
        TreeNode root = bstFromPreorder(preorder);

        // ???? ????
        System.out.print("main <<<  inOrder: ");
        inOrder(root);
    }

We start by reading and splitting the line that holds the results of the pre order traversal of the BST. We then allocate an array to hold the integer values and populate it. We are ready to call the function we need to implement. When done, I like to display the results. We do this by performing a in order BST traversal. If all is well, the values should display the ascending order. We could check for this and the count of nodes to automatically check if the results are valid. I just use my eyes to check.

    /**
     * BST in order traversal.
     * Recursive call.
     * 
     * !!! This method is not part of the solution !!!
     */
    static void inOrder(TreeNode root) {

        // **** end condition ****
        if (root == null)
            return;

        // **** visit left sub tree ****
        inOrder(root.left);

        // **** visit root ****
        System.out.print(root.val + " ");

        // **** visit right sub tree ****
        inOrder(root.right);
    }

The inOrder() method is not part of the solution. It is part of the test scaffolding. In general I am trying not to put functions used in the test scaffolding, but I thought that based on the requirements it would be nice to include it this time.

    /**
     * Return the root node of a BST that matches the given preorder traversal.
     * According to the problem constraints, there are no empty trees.
     * 
     * Runtime: 0 ms, faster than 100.00% of Java online submissions.
     * Memory Usage: 37 MB, less than 39.24% of Java online submissions.
     */
    static TreeNode bstFromPreorder(int[] preorder) {
        
        // **** populate and return BST (entry for recursive call) ****
        return populate(preorder, new int[] {0}, Integer.MAX_VALUE);
    }

In many cases a recursive approach requires an entry point. In this case we will use the bstFromPreorder() method as the entry point. It makes a single call to the populate() method passing the array with the pre order traversal values and two integers. We will discuss the method next.

    /**
     * Recursive call
     * Runtime: O(n)
     */
    static TreeNode populate(int[] arr, int[] idx, int constraint) {

        // **** visit node ****
        TreeNode node = new TreeNode(arr[idx[0]++]);

        // **** visit left sub tree ****
        if (idx[0] < arr.length && arr[idx[0]] < node.val) {
            node.left = populate(arr, idx, node.val);
        }

        // **** visit right sub tree ****
        if (idx[0] < arr.length && arr[idx[0]] < constraint) {
            node.right = populate(arr, idx, constraint);
        }

        // **** return BST ****
        return node;
    }

This recursive call does not have an explicit end condition. The end conditions are applied before each recursive call is made.

We start by creating the root node of the BST with the value of the first entry in the preorder array and then incrementing the index. The root of the BST is always the first value of a pre order tree traversal.

The reason we use an integer array for the second argument, is due to the fact that it will be changing as we traverse the preorder array. We could have used an external global variable.

The third and last argument is required to address the changing needs when we switch from traversing the left sub tree to the right. The reason is that all node values on the left sub tree, are less than the root value, while there is no limit to the values of the nodes on the right sub tree. This is why the requirements emphasize such property of BSTs.

When all is said and done, we return the BST we generated.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!

One last thing, many thanks to all 4,478 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

John

john.canessa@gmail.com

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.