Tree Traversals

Adapted from the Goodrich and Tamassia lecture on Trees

---

Trees

• a tree represents a hierarchy
• example: organizational structure of a corporation

• example: table of contents of a book

---

Another Example

• Unix or DOS/Windows file system

---

Terminology

• A is the root node of the tree.
• B is the parent of D and E.
• C is the sibling of B.
• D and E are the children of B.
• D, E, F, G, and I are external nodes or leaves.
• A, B, C, and H are internal nodes.
• The depth (i.e. level) of E is 2.
• The height of the tree is 3.
• The degree of node B is 2.

Property: (# edges) = (# nodes) – 1

---

Depth and Height Let v be a node of tree T.
"Intuitive" definition of depth:
The depth of v is the number of ancestors of v, excluding v itself.
Recursive definition of depth:
Depth of v = 
"Intuitive" definition of height:
Height of tree T = height of the root node of T
                           = maximum depth of the external nodes.
Recursive definition of height:
Height of v = 

---

Binary Trees

• A binary tree is a tree in which all internal nodes are of degree 2.
• Recursive definition of binary tree:

• A binary tree is either
• an external node (i.e., leaf) or
• an internal node (the root of the tree) and two binary trees, the left subtree and the right subtree.

---

Binary Tree Example

• arithmetic expression

((((3´(1+(4+6)))+(2+8))´5)+(4´(7+2)))
 

---

Properties of Binary Trees

• (# external nodes) = (# internal nodes) + 1
• (# nodes at level i) £ 2ⁱ
• (# external nodes) £ 2^(height)
• (height) ³ log₂(# external nodes)
• (height) ³ log₂(# nodes+1)– 1
• (height) £ (# internal nodes) = ((# nodes) –1)/2

---

Properties of Binary Trees (cont.)

• Define:

• h = height
• n = # nodes
• n_i = # internal nodes
• n_e = # external nodes

• Using n = n_i + n_e, it immediately follows that

• n_i = n_e – 1, or n_e = n_i + 1

Þ n = 2n_i + 1

                                                 (1)

By definition we have that

                                             (2)

Note that .                                 (3)

Taking logs of the inequality (3), From (2) and (1),

---

The Tree ADT

• The nodes of a tree are viewed as Positions.
• Generic container methods:

• size(), isEmpty(), elements(), newContainer()

• Positional container methods:
• positions(), replace(p,e), swap(p,q)
• Query methods:
• isRoot(p), isInternal(p), isExternal(p)
• accessor methods
• root(), parent(p), children(p), siblings(p)

• update methods are application specific.

 Interface InspectableTree

---

The Binary Tree ADT

• Extends the InspectableTree ADT
• Accessor methods:
• leftChild(p), rightChild(p), sibling(p)
• Update methods:
• expandExternal(p), removeAboveExternal(p), cut(p), link(p,T), replaceSubtree(p,T).
• other, application-specific methods (e.g. AVL trees).

 
 Interface BinaryTree

---

Method void expandExternal(Position p)

• before:

• Position p points to an external node storing the string "CJ".

• after:

Position p points to the same node storing the same object. Now, however, the formerly external node has two external children.

---

Method void removeAboveExternal(Position w)

• Before:

• w is the Position that is passed as a parameter, z is its sibling, v its parent, and u its grandparent.

• After:
• The parameter-position w and its parent v have been deleted. The node at position z has taken v’s place as the child of u.

---

Method BinaryTree cut(Position subTreeRoot)

• Before

• After

---

Method void link(Position mustBeExternal, BinaryTree newSubTree)

• Before

• After

---

Method BinaryTree replaceSubtree(Position subTreeRoot, BinaryTree newSubTree)

• before:

• after:

---

Traversing Trees

• preorder traversal

Algorithm preOrder(v)
    "visit" node v
    for each child w of v do
        recursively perform preOrder(w)

• Example: reading a document from beginning to end.

• Analysis of preorder traversal:

• Assume that visiting a node takes O(1) time.
• The nonrecursive part of preOrder on node v then takes O(c_v) time, where c_v = # children of v.
• .
• Visiting all nodes in the tree takes O(n) time.
• Same results hold for postorder traversal.

---

Traversing Trees (cont.)

• postorder traversal

Algorithm postOrder(v)
    for each child w of v do
       recursively perform postOrder(w)
    "visit" node v

• Example: du command in Unix

---

Traversing Binary Trees

• preorder traversal of a binary tree

Algorithm binaryPreOrder(T,v)
    "visit" node v
    binaryPreOrder(T,T.leftChild(v))
    binaryPreOrder(T,T.rightChild(v))

• inorder traversal of a binary tree

Algorithm inOrder(T,v)
    inOrder(T,T.leftChild(v))
    "visit" node v
    inOrder(T,T.rightChild(v))  Lafore Binary Tree Applet

• postorder traversal of a binary tree

AlgorithmbinaryPostOrder(T,v)
    binaryPostOrder(T,T.leftChild(v))
    binaryPostOrder(T,T.rightChild(v))
    "visit" node v

---

Evaluating Arithmetic Expressions

• Specialization of a postorder traversal on binary trees.

Algorithm evaluateExpression(v)
    if v is an external node
     return the variable stored at v
    else
        let o be the operator stored at v
        x ¬ evaluateExpression(T,T.leftChild(v))
        y ¬ evaluateExpression(T,T.rightChild(v))
        returnxoy

---

Euler Tour Traversal

• Generic traversal of a binary tree.

• The preorder, inorder, and postorder traversals are special cases of the Euler tree traversal.

• "Walk around" the tree and visit each node three times:
• on the left
• from below
• on the right

Algorithm eulerTour(T,v)
    if T.isExternal(v)
        visit node v
    else
        visit node v from the left
        eulerTour(T, T.leftChild(v))
        visit node v from below
        eulerTour(T, T.rightChild(v))
        visit node v from the right

---

Printing an Arithmetic Expression

• An example of an Euler tour traversal

• Print "(" before traversing the left subtree.
• Print the operator or operand after traversing the left subtree and before traversing the right subtree.
• Print ")" after traversing the right subtree.

((((3´(1+(4+6)))+(2+8))´5)+(4´(7+2)))

---

Template Method Pattern

• Generic computation mechanism that can be specialized by redefining certain steps.

• Implemented via an abstract Java class with methods that can be redefined by its subclasses.

public abstract class BinaryTreeTraversal {
    // Template for algorithms traversing a binary tree
    //using an Eulertour. The subclasses of this class will
    // redefine some of the methods of this class to create a specific traversal.
    protected BinaryTree tree;
    public Object execute(BinaryTree T) {
        tree = T;
        return null; // nothing interesting to return
    }

---

Template Method Pattern (cont.)

    protected Object traverseNode(Position p) {
        TraversalResult r = new TraversalResult();
        if (tree.isExternal(p)) {
            external(p, r);
        }
        else {
            left(p, r);
            r.leftResult = traverseNode(tree.leftChild(p));
            // recursive traversal
            below(p, r);
            r.rightResult = traverseNode(tree.rightChild(p));
            // recursive traversal
            right(p, r);
        }
        return r.finalResult;
    }     // methods that can be redefined by the subclasses
    protected void external(Position p, TraversalResult r){}
    protected void left(Position p, TraversalResult r) {}
    protected void below(Position p, TraversalResult r) {}
    protected void right(Position p, TraversalResult r) {}
}

---

Specializing the Generic Binary Tree Traversal

• Printing an arithmetic expression

public class PrintExpressionTraversal extends BinaryTreeTraversal {
    // This traversal specialized BinaryTreeTraversal to
    // print out the arithmetic expression stored in the tree.
    // It assumes that the elements stored in the nodes of
    // the tree support a toString method that prints the
    // variable at an external node or the operator at the
    // internal node.
    public Object execute(BinaryTree T) {
        super.execute(T);
        System.out.print("Expression: " );
        traverseNode(T.root());
        System.out.println();
        return null; // nothing interesting to return
    }     protectedvoid external(Position p, TraversalResult r) {
        System.out.print(p.element());
    }
    protectedvoid left(Position p, TraversalResult r) {
        System.out.print("(");
    }

---

Specializing the Generic Binary Tree Traversal (cont.)     protectedvoid below(Position p, TraversalResult r) {
        System.out.print(p.element());
    }
    protectedvoid right(Position p, TraversalResult r) {
        System.out.print(")");
    }
}
 TraversalResult.java
 EvaluateExpressionTraversal.java
 OperatorInfo.java
 AdditionOperator.java
 MultiplicationOperator.java

---

Linked Data Structure for Binary Trees
 Node.java
 Class LinkedBinaryTree