Tree Programming Questions

[raveena]

Implement the codes (with complexitites)

1. In-order tree traversal (both recursive and non-recursive)

2. Pre-order Tree traversal

3. Post-order tree traversal

4. Level-order traversal (a.k.a breadth first traversal of tree). i.e., First print level 0 nodes(root only), then level 1 nodes (children of root), then level 2 nodes, and so on.

5. size: number of elements present in a tree. Calculate size of a tree

6. max depth/height: height of longest branch of the tree (i.e., root to the bottom-most node). Find height of a tree

7. identical trees: when the 2 trees have same node-values and arrangement of nodes in both the trees is also same. EG:

Tree1:   5                       identical:  5                  not ident:  5
          / \                                    / \                               / \
         3  4                                   3  4                             4  3
Determine if 2 trees are identical

8. Appropriate way to delete a tree: directly or node by node ??
Remember that before deleting a parent we should delete the children of the parent first. So which traversal: pre,in,post?

9. Mirror: of a tree is another tree with left and right children of all non-leaf nodes interchanged.

         1                                 mirror:  1
        / \                                           / \
       3   2                                        2   3
             /\                                      /\
            5  4                                   4  5

10. Print all the roof-to-leaf paths of a tree