Trees and Traversals

Define Rules.

Rooted Tree

Definitions

Representing Rooted Trees

tree1
class Node{

    Object item;
    Node parent;
    Node firstChild;
    Node nextSibling; // this can become singly linked list
    // nextsibling can keep track so a node can have many //childs. Essentially a singly linked list with first child as head of LL.


}

class Tree {
    Node root;
    int size;
}

Traversal

Frequent Traversal

Preorder Traversal
- Visit each node before recursively visiting its children 
- Left to Right
- Root Visited First
- Visited only once
- Takes O(N) for entire traversal - Linear Time

 class Node {
    public void preorder(){
        this.visit();
        if(firstChild!=null){
            firstChild.preorder();
        }
        if(nextSibiling !=null){
            nextSibling.preorder();
        }
    }
 }

Visualize Preorder Traversal. Order of processing.

        1
     2     6 
   3 4 5  7 8 
PostOrder Traversal
public void postorder(){

    if(firstchild !=null){
        firstChild.postorder();
    }

    this.visit();

    if(nextsibling !=null){
        nextsibling.postorder();
    }

}

Visualize


         8
      4      7
    1 2 3   5  6
InOrder Traversal ( only in Binary Trees )

Visualize parsing the expression tree.

       +
     *   ^
   3  7  4 2 
Level order Traversal