### Question

A tree has a special property where leaves are represented with ‘2’ and non-leaf with ‘1’. Each node has either 0 or 2 children. If given preorder traversal of this tree, construct the tree.

Example: Given Pre Order string => 12122, output:

```
1
/ \
2 1
/ \
2 2
```

### Analysis

In normal scenario, it’s not possible to detect where left subtree ends and right subtree starts using only pre-order traversal. But here, we are given a special property. Since every node has either 2 children or no child, we can surely say that if a node exists then its sibling also exists.

Keep a public variable and build the tree recursively until the list finishes.

### Code

```
ListNode list = null; // this is the input list public variable
public TreeNode main(ListNode input) {
list = input;
return constructTree();
}
private TreeNode constructTree() {
if (list == null) {
return null;
}
TreeNode root = new TreeNode(list.val);
list = list.next;
if (root.val == 1) {
root.left = constructTree();
root.right = constructTree();
}
return root;
}
```