Question

link

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;
}