Tree Base

discussion.txt

The important thing isn't the solution.

Discussing more/less a train of thought as to how to come up with that solution, though:

Stack <--> DFS algo.
Queue <--> BFS algo.

You should be able to figure out pseudocode along the lines of:

PreOrder(TreeNode t):
  output(t.value)
  PreOrder(t.left)
  PreOrder(t.right)

(What's "output"? Well. One way would be to add to some List, then get the list's iterator.
 What we do in the above code is more subtle, in that it's the return value of "next"..).
But, yeah, the Iterator can't quite handle that recursively defined solution.

The pseudocode needs to change to be like:

PreOrder(TreeNode t):
  Stack s
  s.push(t);
  
  while s not empty:
    TreeNode t = s.pop()
    
    output(t)
    s.push(t.right) } if values
    s.push(t.left)  }  not null

That's the same as the above. The leap from that pseudocode to the Iterator code
isn't tiny, but you should have a much better idea of it now.




When I demonstrated in class, I was unsure of whether I would need any additional data structures to help with
iterating through the stack. BFS/DFS, you don't.
We prob'ly need to with an InOrder iterator.

Recursive Pseudocode would look like:

InOrder(TreeNode t):
  InOrder(t.left)
  output(t)
  InOrder(t.right)

And so an iterative form of this?
Recursive, so we might want to use a stack; but now we want to exhause all of left before we exhaust all of right.
There are different ways to do this.

A "cheap" way might be to have a helper method like
  private static Iterator<T> iteratorForXOrder(TreeNode tn);
And then we can try and look at the left/right iterators of the children in a recursive manner.
The code for that is going to be slightly messy, but it would closely follow the logic of the above code.

But to do it iteratively?
I get the impression that, aside from a Stack, another data structure is needed.
Consider that.

Tree.java

package sg.nus.edu.cs2020.scratch;

import java.util.*;

// In class I forgot to put the generics as part of Tree.
// (And so my code was wrong -- exposing TreeNode to outside of Tree is 'bad').
// This is how you might do that:
public class Tree<T extends Comparable<T>> extends TreeBase<T> {

	@Override
	public Iterator<T> getPreOrderIterator() {
		// Pre-Order:
		// "visit" tree's node first, then nodes of children.
		
		final Stack<TreeNode> stack = new Stack<TreeNode>();
		
		// push root node into stack to 'initialise' our algorithm.
		stack.push(this.getRoot());
		
		return new Iterator<T>() {

			@Override
			public boolean hasNext() {
				return !stack.isEmpty();
			}

			@Override
			public T next() {
				// Get (and keep track of) the top value from the stack.
				// n.b. we don't just return it immediately, since we need to deal
				// with other things.
				TreeNode root = stack.pop();
				
				TreeNode left = root.getLeftChild();
				TreeNode right = root.getRightChild();
				
				// Since a stack is LIFO, and we want to visit left before right,
				// we push right in before left.
				
				// Only push onto stack if non-null
				if (right != null) {
					stack.push(right);
				}
				if (left != null) {
					stack.push(left);
				}
				
				return root.getValue();
			}

			@Override
			public void remove() {
				throw new UnsupportedOperationException();
			}
		};
	}

	@Override
	public Iterator<T> getLevelOrderIterator() {
		// Level-Order:
		// "visit" nodes in BFS, using a queue.
		
		// Copy-paste from above code.
		// * Use Eclipse: refactor-> rename from stack to 'queue'.
		// * Change from Stack to Queue, LinkedList;
		// * Change methods from push/pop to add/poll
		// * Change order of left/right.
		
		final Queue<TreeNode> queue = new LinkedList<TreeNode>();
		
		// push root node into stack to 'initialise' our algorithm.
		queue.add(this.getRoot());
		
		return new Iterator<T>() {

			@Override
			public boolean hasNext() {
				return !queue.isEmpty();
			}

			@Override
			public T next() {
				TreeNode root = queue.poll();
				
				TreeNode left = root.getLeftChild();
				TreeNode right = root.getRightChild();
				
				if (left != null) {
					queue.add(left);
				}
				if (right != null) {
					queue.add(right);
				}
				
				return root.getValue();
			}

			@Override
			public void remove() {
				throw new UnsupportedOperationException();
			}
		};
	}

}

TreeBase.java

package sg.nus.edu.cs2020.scratch;

import java.util.Iterator;

/**
 * Generic Tree Class.
 * 
 * Trees comprise one node, where a node is either the empty node, or a node
 * containing one value of type T and two child nodes.
 * 
 * @author Joel Low <joel.low@nus.edu.sg>
 *
 * @param <T> The type of the value held at each tree node.
 */
public abstract class TreeBase<T extends Comparable<T>> {
	/**
	 * The base type of each node in this tree. This is the publicly accessible
	 * interface to each node in the tree.
	 * 
	 * @author Joel Low <joel.low@nus.edu.sg>
	 */
	public abstract class TreeNode {
		/**
		 * Gets the value associated with this node.
		 * 
		 * @return The value associated with this node.
		 */
		public abstract T getValue();
		
		/**
		 * Gets the root of the left subtree of this node.
		 * 
		 * @return The tree node representing the root of the left subtree.
		 */
		public abstract TreeNode getLeftChild();
		
		/**
		 * Gets the root of the right subtree of this node.
		 * 
		 * @return The tree node representing the root of the right subtree.
		 */
		public abstract TreeNode getRightChild();
	}
	
	/**
	 * The concrete type of each node in this tree.
	 * 
	 * @author Joel Low <joel.low@nus.edu.sg>
	 */
	protected class TreeNodeImpl extends TreeNode {
		/**
		 * Constructs a new tree node with the given value.
		 * 
		 * @param value The value for the node.
		 */
		public TreeNodeImpl(T value) {
			this.value = value;
		}
		
		@Override
		public T getValue() {
			return value;
		}

		@Override
		public TreeNode getLeftChild() {
			return leftChild;
		}
		
		@Override
		public TreeNode getRightChild() {
			return rightChild;
		}
		
		/**
		 * Inserts the given value into the tree.
		 * @param value
		 */
		public void insert(T value) {
			int comparison = value.compareTo(this.value);
			if (comparison < 0) {
				//Left subtree
				if (leftChild == null) {
					leftChild = new TreeNodeImpl(value);
				} else {
					leftChild.insert(value);
				}
			} else if (comparison > 0) {
				//Right subtree
				if (rightChild == null) {
					rightChild = new TreeNodeImpl(value);
				} else {
					rightChild.insert(value);
				}
			} else {
				//Equal. No-op
			}
		}
		
		/**
		 * The value held by this node. This field is public because this is a
		 * private class and thus the only class able to access this field is
		 * the Tree<T> class.
		 */
		public T value;
		
		/**
		 * The left child of this node.
		 */
		public TreeNodeImpl leftChild;
		
		/**
		 * The right child of this node.
		 */
		public TreeNodeImpl rightChild;
	}
	
	/**
	 * Constructor. Creates an empty tree.
	 */
	public TreeBase() {
	}
	
	/**
	 * Gets the root of the tree.
	 * 
	 * @return The root of the tree.
	 */
	public TreeNode getRoot() {
		return root;
	}
	
	/**
	 * Inserts the given value into the tree. After this operation, the given
	 * value (as compared via compareTo) will be found in some node of the tree.
	 * @param value
	 */
	public void insert(T value) {
		if (root == null) {
			root = new TreeNodeImpl(value);
		} else {
			root.insert(value);
		}
	}
	
	/**
	 * Gets a pre-order iterator for the given tree.
	 * 
	 * @return A pre-order iterator for this tree.
	 */
	public abstract Iterator<T> getPreOrderIterator();
	
	/**
	 * Gets a level-order iterator for the given tree.
	 * 
	 * @return A level-order iterator for this tree.
	 */
	public abstract Iterator<T> getLevelOrderIterator();
	
	/**
	 * The root of the tree.
	 */
	protected TreeNodeImpl root;
}