> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/trees/construct-a-special-tree-from-given-preorder-traversal.md).

# 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
```

```java
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);
    }
}
```