Binary Tree Construct from TRAVERSAL SEQUENCES

Binary Tree Construct from TRAVERSAL SEQUENCES:

http://www.geeksforgeeks.org/if-you-are-given-two-traversal-sequences-can-you-construct-the-binary-tree/

1.Tree from Preorder and inorder:

http://algorithms.tutorialhorizon.com/construct-a-binary-tree-from-given-inorder-and-depth-first-search/

http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/

2. Binary Tree from Inorder and Postorder

http://www.geeksforgeeks.org/construct-a-binary-tree-from-postorder-and-inorder/

3. Binary Tree from Inorder and Level order

http://algorithms.tutorialhorizon.com/construct-a-binary-tree-from-given-inorder-and-level-order-traversal/

4. Full Binary Tree from Preorder and Postorder

http://www.geeksforgeeks.org/full-and-complete-binary-tree-from-given-preorder-and-postorder-traversals/

5. Generate all possible Binary trees from given Inorder Traversal

http://www.geeksforgeeks.org/find-all-possible-trees-with-given-inorder-traversal/

6. Construct a special tree from given preorder traversal

http://www.geeksforgeeks.org/construct-a-special-tree-from-given-preorder-traversal/

7. BST from given Pre order Traversal

http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/
http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversal-set-2/

Special Tree Construction

A tree has a special property where leaves are represented with ‘L’ and non-leaf with ‘N’. Each node has either 0 or 2 children. If given preorder traversal of this tree, construct the tree
Example:
Given Pre Order string => NLNLL

o/p tree:

Strategy:

Firstly, we should see how pre-order traversal is arranged. Pre-order traversal means first put root node, then pre order traversal of left subtree and then pre order traversal of right subtree. As shown in below figure:

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. So every time we are computing a subtree, we need to compute its sibling subtree as well.

Secondly, whenever we get ‘L’ in the input string, that is a leaf so we can stop for a particular subtree at that point. So after this ‘L’ node (left child of its parent ‘L’), it’s sibling starts. If ‘L’ node is right child of its parent, then we need to go up in the hierarchy to find next subtree to compute.

Keeping above invariant in mind, we can easily determine, when a subtree ends and next start. It means that we can give any start node to our method and it can easily complete the subtree it generates w/o going outside its nodes.

We just need to take care, that we are passing correct start nodes to different subtrees.