Construct a special tree from given preorder traversal

Given an array ‘pre[]’ that represents Preorder traversal of a spacial binary tree where every node has either 0 or 2 children. One more array ‘preLN[]’ is given which has only two possible values ‘L’ and ‘N’. The value ‘L’ in ‘preLN[]’ indicates that the corresponding node in Binary Tree is a leaf node and value ‘N’ indicates that the corresponding node is non-leaf node. Write a function to construct the tree from the given two arrays.

Example:

Input:  pre[] = {10, 30, 20, 5, 15},  preLN[] = {'N', 'N', 'L', 'L', 'L'}
Output: Root of following tree
          10
         /  \
        30   15
       /  \
      20   5
class Solution {
    static int index;

    private static Node helper(int[] preData, String[] lnData) {
        if (index >= preData.length)
            return null;
        if (lnData[index].equals("L"))
            return new Node(preData[index++], null, null);
        Node root = new Node(preData[index++], null, null);
        root.left = helper(preData, lnData);
        root.right = helper(preData, lnData);
        return root;
    }

    private static Node construct(int[] preData, String[] lnData) {
        index = 0;
        return helper(preData, lnData);
    }
}

Last updated