Tree Traveral

Four ways to iterate over all the element of this BST?

1. Level-order traversal (breath first traversal)
2. In-order traversal (depth first)
3. Pre-order traversal (depth first)
4. Post-order traversal (depth first)

Level-order traversal

Visits the nodes level by level from left to right starting from the root.

Iterative implementation: Use a queue. Start at the root. Add it to the queue. When you take a value out of the queue, insert its children in the queue (they will go to the back).

Recursive implementation: pass a value up and down, that indicates what level you are at.

In-order traversal

Produce the sequence in order. For every node, visit the left subtree, then the node, then the right subtree.

The recursive definition: for each node, recursively perform in-order traversal of the subtree rooted at its left child, then visit the root (the node itself), then recursively perform in-order traversal of the subtree rooted at its right child.

• Summary: left, root, then right.

private void printInOrder() {  
 	printInOrder(root);  
}  
  
private void printInOrder(Node<T> node) {
	if (node == null) {
		return null;
	}
	
	printInOrder(node.left);  
	System.out.print(node.data + " ");  
	printInOrder(node.right);  
}

The base case is when the tree is empty.

The iterative implementation is much more difficult. You will need an auxciliary data structure in the iterator class to keep track of some of the nodes as you traverse the trees so that you can visit those nodes later. The auxiliary data structure will make a less efficient iterator (space complexity >O(1)).

• Pattern: keep going left as much as you can until you hit null then start printing backwards.
• We will need a stack, a cursor that starts at the root. Start by pushing the cursor onto the stack, and then traverse as far as you can to the left, adding things onto the stack along the way. Set the cursor to the stack pop, and print the cursor, then push the right side.

Pre-order traversal

For every node, visit it, then visit its left subtree, then visit its right subtree.

• Summary: root, left, right

To implement switch the lines of the in-order traversal.

Post-order traversal

For ever node, visit its left subtree, then visit its right subtree, then visit the node.

• Summary: left, right, root

To implement switch the lines of the in-order traversal.

Tree Terminology

Suppose $n_1, n_2, ..., n_k$ is a sequence of nodes in a tree. It's called the path from $n_1$ to $n_k$.

The length of the path is $k-1$ where $k$ is the number of nodes on it.

• A path with one node has a length of zero.

The height of a node $n$ is the length of a longest path from $n$ to a leaf.

• The height of a tree is the height of its root.
• Recursively define the height of a node: height(n) is zero when n is the leaf, or 1+max(height of child) when n=/= leaf.
• For us, height of a leaf is zero. In some references, the height of the node includes the node. In that case, the height of a leaf is 1.

The depth, or level, of a node $n$, is the length of the path from the root to n.

• The height of a tree is the depth of its deepest nodes.
• Recursively define the depth of a node: height (n) is zero when n = leaf and 1+depth(parent(n)) when n=/=leaf.
• For us, depth will start at 0. (in other references, the depth of a node includes the node.)

Perfect Binary Tree

Is a binary tree in which all interior nodes have two children, and all leaves has the same depth or same level. The height of a perfect binary tree is $O(lg n)$, where n is the number of nodes. The total number of nodes for a full binary tree with depth $d$ is $n = 2^0 + 2^1 + ... + 2^d = 2^d+1-1$

Every operation will be at most O(h).

To get logarithmic operations, you should try your best to get it to look like a perfect binary tree.

• Try for a balanced search tree.

Consideratios

What if you want a parent with more than two children?

1. The node holds data and a collection of all its children
2. The node only knows the left most child, and the child knows its immediate siblings.