Binary Tree Construction and Traversals

Tree Construction

1.  Given a sorted linked list, construct a Binary Search Tree.

2.  Given a doubly linked list, construct a Binary Search Tree and vice-a-versa.

3. Construct a  Binary Search Tree  given a preorder and an inorder traversal of the tree.

  Example:
    

   Inorder:  B D A E F C
   Preorder:  A B D C E F

   Java source code:  Main class -> TreeConstructionInorderPreorder.java
                                Other classes -> BinaryTree.java, Node.java  
   Input File: TreeTraInput.txt

Traversals

Types of Binary Tree

    1. Normal Binary Tree

    2. Binary Search Tree

    3. Threaded Binary Tree

Type of Traversals ( Wiki )

    Depth-First

         1.  Preorder

         2.  Inorder

         3.  Postorder

  

    Breadth First 

        4. Level order  

        5. Zig-Zag 

    

Methodology

    1. Recursive 

    2. Iterative using Stack
    3. Inorder tree traversal without recursion and  use of stack ( Hint : Morris Traversal, Morris Traversal 2)