# Save The Trees Challenge

Page 1 of 1

## 13 Replies - 3723 Views - Last Post: 20 April 2011 - 10:54 AM

### #1 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12680
• Posts: 45,863
• Joined: 27-December 08

# Save The Trees Challenge

Posted 18 April 2011 - 02:30 PM

It's time to go green with some of my personal favorite Al Goreithms. For this challenge, post something you have done with a Tree data structure. It can be implementing a specific Tree like an AVL Tree to an algorithm like Prim's algorithm, or something completely different. The only constraint is that you use Trees, your submission is written in a programming language, not simply pseudo-code, and you post it using spoiler tags. So let's have some fun and fight global warming!

Submission 1:
Spoiler

Submission 2:
Spoiler

Is This A Good Question/Topic? 2

## Replies To: Save The Trees Challenge

### #2 Sergio Tapia

• D.I.C Lover

Reputation: 1258
• Posts: 4,168
• Joined: 27-January 10

## Re: Save The Trees Challenge

Posted 18 April 2011 - 07:41 PM

POPULAR

My attempt at using trees in an application:

```Console.WriteLine(@"

,
dM
MMr
4MMML                  .
MMMMM.                xf
.              "M6MMM               .MM-
Mh..          +MM5MMM            .MMMM
.MMM.         .MMMMML.          MMMMMh
)MMMh.        MM5MMM         MMMMMMM
3MMMMx.     'MMM3MMf      xnMMMMMM"
'*MMMMM      MMMMMM.     nMMMMMMP"
*MMMMMx    "MMM5M\    .MMMMMMM=
*MMMMMh   "MMMMM"   JMMMMMMP
MMMMMM   GMMMM.  dMMMMMM            .
MMMMMM  "MMMM  .MMMMM(        .nnMP"
..          *MMMMx  MMM"  dMMMM"    .nnMMMMM*
"MMn...     'MMMMr 'MM   MMM"   .nMMMMMMM*"
"4MMMMnn..   *MMM  MM  MMP"  .dMMMMMMM""
^MMMMMMMMx.  *ML "M .M*  .MMMMMM**"
*PMMMMMMhn. *x > M  .MMMM**""
""**MMMMhx/.h/ .=*"
.3P"%....
nP"     "*MMnx

");

```

This post has been edited by Sergio Tapia: 18 April 2011 - 08:21 PM

### #3 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12680
• Posts: 45,863
• Joined: 27-December 08

## Re: Save The Trees Challenge

Posted 18 April 2011 - 08:17 PM

LOL! Trees Sergio, not weed!

### #4 Brewer

• Awesome

Reputation: 182
• Posts: 1,044
• Joined: 14-June 10

## Re: Save The Trees Challenge

Posted 18 April 2011 - 10:46 PM

On an unrelated note, I don't think I've ever seen macosxnerd101 use "lol" in one of his posts.

Maybe I'll get around to trying something of my way.

### #5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12680
• Posts: 45,863
• Joined: 27-December 08

## Re: Save The Trees Challenge

Posted 19 April 2011 - 01:35 PM

Let's get some more entries everyone! Trees are some fun stuff! Surely somebody has done something with Trees like tree traversals, reverse polish notation, etc. Let's have some fun with this!

I've got another submission, for binary tree rotations:
Spoiler

### #6 dorknexus

Reputation: 1272
• Posts: 4,625
• Joined: 02-May 04

## Re: Save The Trees Challenge

Posted 19 April 2011 - 03:04 PM

Quote

LOL! Trees Sergio, not weed!

Pssh. If you were in the know, you'd know that trees are synonymous. People who smoke trees are are called Ents. YOU LOSE.

### #7 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12680
• Posts: 45,863
• Joined: 27-December 08

## Re: Save The Trees Challenge

Posted 19 April 2011 - 03:09 PM

Actually, this is an Ent.

### #8 Brewer

• Awesome

Reputation: 182
• Posts: 1,044
• Joined: 14-June 10

## Re: Save The Trees Challenge

Posted 19 April 2011 - 03:21 PM

Lord of the Rings ftw.

• MrCupOfT

Reputation: 2298
• Posts: 9,535
• Joined: 29-May 08

## Re: Save The Trees Challenge

Posted 19 April 2011 - 04:08 PM

See Blog Post: Generic Binary Tree

### #10 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12680
• Posts: 45,863
• Joined: 27-December 08

## Re: Save The Trees Challenge

Posted 19 April 2011 - 04:16 PM

Awesome entry Adam! It was nice to see the BTree reprsented as well!

• MrCupOfT

Reputation: 2298
• Posts: 9,535
• Joined: 29-May 08

## Re: Save The Trees Challenge

Posted 19 April 2011 - 04:19 PM

I don't think it a proper b-tree. Is it?

### #12 Nikitin

• D.I.C Regular

Reputation: 56
• Posts: 264
• Joined: 02-August 10

## Re: Save The Trees Challenge

Posted 19 April 2011 - 06:10 PM

That's not a B-Tree.

### #13 Ronald91

Reputation: 11
• Posts: 31
• Joined: 26-April 09

## Re: Save The Trees Challenge

Posted 20 April 2011 - 10:29 AM

Here is an implementation of a binary tree that I used recently.

```package TreePackage;
import java.util.Iterator;
import java.util.NoSuchElementException;
import StackAndQueuePackage.*;

/**
* A class that implements the ADT binary tree.
*/
public class BinaryTree<T> implements BinaryTreeInterface<T>, java.io.Serializable
{
private BinaryNodeInterface<T> root;

public BinaryTree()
{
root = null;
} // end default constructor

public BinaryTree(T rootData)
{
root = new BinaryNode<T>(rootData);
} // end constructor

public BinaryTree(T rootData, BinaryTree<T> leftTree,
BinaryTree<T> rightTree)
{
privateSetTree(rootData, leftTree, rightTree);
} // end constructor

public void setTree(T rootData)
{
root = new BinaryNode<T>(rootData);
} // end setTree

public void setTree(T rootData, BinaryTreeInterface<T> leftTree,
BinaryTreeInterface<T> rightTree)
{
privateSetTree(rootData, (BinaryTree<T>)leftTree,
(BinaryTree<T>)rightTree);
} // end setTree

// 26.08
private void privateSetTree(T rootData, BinaryTree<T> leftTree,
BinaryTree<T> rightTree)
{
root = new BinaryNode<T>(rootData);

if ((leftTree != null) && !leftTree.isEmpty())
root.setLeftChild(leftTree.root);

if ((rightTree != null) && !rightTree.isEmpty())
{
if (rightTree != leftTree)
root.setRightChild(rightTree.root);
else
root.setRightChild(rightTree.root.copy());
} // end if

if ((leftTree != null) && (leftTree != this))
leftTree.clear();

if ((rightTree != null) && (rightTree != this))
rightTree.clear();
} // end privateSetTree

private BinaryNode<T> copyNodes() // not essential
{
return (BinaryNode<T>)root.copy();

} // end copyNodes

// 26.09
public T getRootData()
{
T rootData = null;

if (root != null)
rootData = root.getData();

return rootData;
} // end getRootData

// 26.09
public boolean isEmpty()
{
return root == null;
} // end isEmpty

// 26.09
public void clear()
{
root = null;
} // end clear

// 26.09
protected void setRootData(T rootData)
{
root.setData(rootData);
} // end setRootData

// 26.09
protected void setRootNode(BinaryNodeInterface<T> rootNode)
{
root = rootNode;
} // end setRootNode

// 26.09
protected BinaryNodeInterface<T> getRootNode()
{
return root;
} // end getRootNode

// 26.10
public int getHeight()
{
return root.getHeight();
} // end getHeight

// 26.10
public int getNumberOfNodes()
{
return root.getNumberOfNodes();
} // end getNumberOfNodes

// 26.12
public void inorderTraverse()
{
inorderTraverse(root);
} // end inorderTraverse

private void inorderTraverse(BinaryNodeInterface<T> node)
{
if (node != null)
{
inorderTraverse(node.getLeftChild());
System.out.println(node.getData());
inorderTraverse(node.getRightChild());
} // end if
} // end inorderTraverse

public Iterator<T> getPreorderIterator()
{
return new PreorderIterator();
} // end getPreorderIterator

// 26.13
public Iterator<T> getInorderIterator()
{
return new InorderIterator();
} // end getInorderIterator

public Iterator<T> getPostorderIterator()
{
return new PostorderIterator();
} // end getPostorderIterator

public Iterator<T> getLevelOrderIterator()
{
return new LevelOrderIterator();
} // end getLevelOrderIterator

/*
// 26.14 ITERATIVE
public void inorderTraverse()
{
StackInterface<BinaryNodeInterface<T>> nodeStack =
BinaryNodeInterface<T> currentNode = root;

while (!nodeStack.isEmpty() || (currentNode != null))
{
// find leftmost node with no left child
while (currentNode != null)
{
nodeStack.push(currentNode);
currentNode = currentNode.getLeftChild();
} // end while

// visit leftmost node, then traverse its right subtree
if (!nodeStack.isEmpty())
{
BinaryNodeInterface<T> nextNode = nodeStack.pop();
assert nextNode != null; // since nodeStack was not empty
// before the pop
System.out.println(nextNode.getData());
currentNode = nextNode.getRightChild();
} // end if
} // end while
} // end inorderTraverse

public void inorderTraverse() // Q5
{
BinaryNode<T> currentNode = (BinaryNode<T>)root;//(BinaryNode<T>)

while (!nodeStack.isEmpty() || (currentNode != null))
{
while (currentNode != null)
{
nodeStack.push(currentNode);
currentNode = (BinaryNode<T>)currentNode.getLeftChild();	//(BinaryNode<T>)
} // end while

if (!nodeStack.isEmpty())
{
BinaryNode<T> nextNode = nodeStack.pop();
assert nextNode != null; // since stack was not empty before pop
System.out.print(nextNode.getData() + " ");
currentNode = (BinaryNode<T>)nextNode.getRightChild();	//(BinaryNode<T>)
}
}
System.out.println();
} // end inorderTraverse

*/
private class PreorderIterator implements Iterator<T>
{
private StackInterface<BinaryNodeInterface<T>> nodeStack;

public PreorderIterator()
{
if (root != null)
nodeStack.push(root);
} // end default constructor

public boolean hasNext()
{
return !nodeStack.isEmpty();
} // end hasNext

public T next()
{
BinaryNodeInterface<T> nextNode;

if (hasNext())
{
nextNode = nodeStack.pop();
BinaryNodeInterface<T> leftChild = nextNode.getLeftChild();
BinaryNodeInterface<T> rightChild = nextNode.getRightChild();

// push into stack in reverse order of recursive calls
if (rightChild != null)
nodeStack.push(rightChild);

if (leftChild != null)
nodeStack.push(leftChild);
}
else
{
throw new NoSuchElementException();
}

return nextNode.getData();
} // end next

public void remove()
{
throw new UnsupportedOperationException();
} // end remove
} // end PreorderIterator

// 26.15
private class InorderIterator implements Iterator<T>
{
private StackInterface<BinaryNodeInterface<T>> nodeStack;
private BinaryNodeInterface<T> currentNode;

public InorderIterator()
{
currentNode = root;
} // end default constructor

public boolean hasNext()
{
return !nodeStack.isEmpty() || (currentNode != null);
} // end hasNext

public T next()
{
BinaryNodeInterface<T> nextNode = null;

// find leftmost node with no left child
while (currentNode != null)
{
nodeStack.push(currentNode);
currentNode = currentNode.getLeftChild();
} // end while

// get leftmost node, then move to its right subtree
if (!nodeStack.isEmpty())
{
nextNode = nodeStack.pop();
assert nextNode != null; // since nodeStack was not empty
// before the pop
currentNode = nextNode.getRightChild();
}
else
throw new NoSuchElementException();

return nextNode.getData();
} // end next

public void remove()
{
throw new UnsupportedOperationException();
} // end remove
} // end InorderIterator

private class PostorderIterator implements Iterator<T>
{
private StackInterface<BinaryNodeInterface<T>> nodeStack;
private BinaryNodeInterface<T> currentNode;

public PostorderIterator()
{
currentNode = root;
} // end default constructor

public boolean hasNext()
{
return !nodeStack.isEmpty() || (currentNode != null);
} // end hasNext

public T next()
{
boolean foundNext = false;
BinaryNodeInterface<T> leftChild, rightChild, nextNode = null;

// find leftmost leaf
while (currentNode != null)
{
nodeStack.push(currentNode);
leftChild = currentNode.getLeftChild();
if (leftChild == null)
currentNode = currentNode.getRightChild();
else
currentNode = leftChild;
} // end while

// stack is not empty either because we just pushed a node, or
// it wasn't empty to begin with since hasNext() is true.
// But Iterator specifies an exception for next() in case
// hasNext() is false.

if (!nodeStack.isEmpty())
{
nextNode = nodeStack.pop();
// nextNode != null since stack was not empty before pop

BinaryNodeInterface<T> parent = nodeStack.peek();

if (parent != null && nextNode == parent.getLeftChild())
currentNode = parent.getRightChild();
else
currentNode = null;
}
else
{
throw new NoSuchElementException();
} // end if

return nextNode.getData();
} // end next

public void remove()
{
throw new UnsupportedOperationException();
} // end remove
} // end PostorderIterator

private class LevelOrderIterator implements Iterator<T>
{
private QueueInterface<BinaryNodeInterface<T>> nodeQueue;

public LevelOrderIterator()
{
if (root != null)
nodeQueue.enqueue(root);
} // end default constructor

public boolean hasNext()
{
return !nodeQueue.isEmpty();
} // end hasNext

public T next()
{
BinaryNodeInterface<T> nextNode;

if (hasNext())
{
nextNode = nodeQueue.dequeue();
BinaryNodeInterface<T> leftChild = nextNode.getLeftChild();
BinaryNodeInterface<T> rightChild = nextNode.getRightChild();

// add to queue in order of recursive calls
if (leftChild != null)
nodeQueue.enqueue(leftChild);

if (rightChild != null)
nodeQueue.enqueue(rightChild);
}
else
{
throw new NoSuchElementException();
}

return nextNode.getData();
} // end next

public void remove()
{
throw new UnsupportedOperationException();
} // end remove
} // end LevelOrderIterator
} // end BinaryTree

```

This post has been edited by Ronald91: 20 April 2011 - 10:30 AM

### #14 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12680
• Posts: 45,863
• Joined: 27-December 08

## Re: Save The Trees Challenge

Posted 20 April 2011 - 10:54 AM

Neat! You even provide an Iterator as well!