views:

149

answers:

3

Is there another way to do this? Just spent 2 hours trying to figure it out. I have a solution (see DumpPostOrder below) however, is there is a better or more efficient method? It feels like there may be. Rules are - no recursion, and the nodes cannot have a visited flag. Ie, you can only use left + right members.

My approach was to destroy the tree in the process. By setting the children of each side to null you can mark the node as traversed once, but I'm also looking at each node with children twice :(. Is there a better faster way? (Comments on my preorder and inorder implementations are appreciated but not necessary (ie, will vote, but not mark answer). Thanks!

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinaryTreeNoRecursion
{
    public class TreeNode<T>
    {
        public T Value { get; set; }

        public TreeNode<T> Left { get; set; }
        public TreeNode<T> Right { get; set; }

        public TreeNode(T inValue)
        {            
            Value = inValue;
        }

        public TreeNode(TreeNode<T> left, TreeNode<T> right, T inValue)
        {
            Left = left;
            Right = right;
            Value = inValue;
        }
    }

    public class BinaryTree<T>
    {
        private TreeNode<T> root;
        public TreeNode<T> Root
        {
            get { return root; }            
        }

        public BinaryTree(TreeNode<T> inRoot)
        {
            root = inRoot;
        }

        public void DumpPreOrder(T[] testme)
        {
            Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
            stack.Push(root);
            int count =0;
            while (true)
            {
                if (stack.Count == 0) break;

                TreeNode<T> temp = stack.Pop();                

                if (!testme[count].Equals(temp.Value)) throw new Exception("fail");

                if (temp.Right != null)
                {
                    stack.Push(temp.Right);
                }

                if (temp.Left != null)
                {
                    stack.Push(temp.Left);
                }

                count++;
            }

        }

        public void DumpPostOrder(T[] testme)
        {

            Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
            TreeNode<T> node = root;
            TreeNode<T> temp;
            int count = 0;
            while(node!=null || stack.Count!=0) 
            {   
                if (node!=null)
                {
                    if (node.Left!=null)
                    {                       
                        temp = node;
                        node = node.Left;
                        temp.Left = null;
                        stack.Push(temp);                        

                    }
                    else
                    if (node.Right !=null)
                    {
                        temp = node;
                        node = node.Right;
                        temp.Right= null;
                        stack.Push(temp);
                    }           
                    else //if the children are null
                    {
                        if (!testme[count].Equals(node.Value)) throw new Exception("fail");
                        count++;
                        if (stack.Count != 0)
                        {
                            node = stack.Pop();
                        }
                        else
                        {
                            node = null;
                        }
                    }       
                }
            }

        }

        public void DumpInOrder(T[] testme)
        {

            Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();            
            TreeNode<T> temp = root;
            int count = 0;
            while (stack.Count!=0 || temp!=null)
            {                
                if (temp != null)
                {                    
                    stack.Push(temp);
                    temp = temp.Left;
                }
                else
                {
                    temp = stack.Pop();
                    if (!testme[count].Equals(temp.Value)) throw new Exception("fail");
                    count++;          
                    temp = temp.Right;
                }

            }
        }

    }


    class Program
    {
        static void Main(string[] args)
        {
            //create a simple tree
            TreeNode<int> node = new TreeNode<int>(100);
            node.Left = new  TreeNode<int>(50);
            node.Right = new  TreeNode<int>(150);
            node.Left.Left = new TreeNode<int>(25);
            node.Left.Right = new TreeNode<int>(75);
            node.Right.Left  = new TreeNode<int>(125);
            node.Right.Right = new TreeNode<int>(175);
            node.Right.Left.Left = new TreeNode<int>(110);

            int[] preOrderResult = { 100, 50, 25, 75, 150, 125, 110, 175};
            int[] inOrderResult = { 25, 50, 75, 100, 110, 125, 150, 175};
            int[] postOrderResult = { 25, 75, 50, 110, 125, 175, 150, 100 };
            BinaryTree<int> binTree = new BinaryTree<int>(node);

            //do the dumps, verify output
            binTree.DumpPreOrder(preOrderResult);
            binTree.DumpInOrder(inOrderResult);
            binTree.DumpPostOrder(postOrderResult);
        }
    }
}
+1  A: 

Seems to me that destroying the tree while traversing it is pretty brutal.

You are currently building a Collection of nodes visited.

You are marking nodes as visited by setting them to null.

Could you not instead check for visitation by checking for the node in your Collection? For efficiency you may need to not use a Stack, but that's an implementation detail.

djna
And when you concede to use _a_ stack, you might as wel use _the_ stack
Henk Holterman
Dyna: Bit confused. How am I building a collection of nodes visited? (I mean, in theory I could). Destroying the tree is brutal and probably not practical, but it was the first thing I thought of when presented with the no flag rule. Another way I was considering is with a second collection or stack.Henk: Sorry, not following how I don't use the stack. And again, I'm looking for insight here, not sarcasm.
Dr.HappyPants
Henk is suggesting that recursion is the answer. Thinking a bit more, I agree with you that a second collection is probably needed.
djna
+1  A: 

Avoiding recursion in this case is probably a bad idea, as previously noted. The system call stack is designed to handle things like this. Destroying your tree is a form of marking nodes.

If you want to use your own stack, then you need to push a bit more more information than just the node. Remember that the system call stack contains the program counter as well as the function parameters (local variables as well bu that is not important here). We could push tuples of the form (PushMyChildren, node), (PrintMe, Node), and when we pop a node of the form (PushMyChildren, node) we push (PrintMe, Node), then (PushMyChildren, right child) and then (PushMyChildren, left child). If the left and right children don't exist don't push them. When we pop a node of the form (PrintMe, Node) we print the node. In pseudo C# (I don't know C# and don't have time to look up the correct types and Syntax).

public void DumpPostOrder(T[] testme)
{
  enum StackState {printNode, pushChildren} 
  Stack< Pair<StackState, TreeNode<T> > > stack = new Stack< Tuple<StackState, TreeNode<T> > >();
  stack.Push(new Pair(pushChildren, root);
  while ( stack.Count != 0 ) {
    Pair<StackState, TreeNode<T> > curr = stack.pop();
    if (curr.First ==  printNode) {
       // process the node in curr.Second
    } else {
       node = curr.Second;
       stack.Push(new Pair(printNode, node));
       if (node.Right != null) {
         stack.Push(new Pair(pushChildren, node.Right))
       }
       if (node.Left != null) {
         stack.Push(new Pair(pushChildren, node.Left))
       }
    }
  }
deinst
This is pretty cool, I'm going to check it out. I have a colleague who also suggested another stack that always pointed at the parent. Re: avoiding recursion, see the comment thread with Henk. Very cool suggestion though, I will look at it tonight.
Dr.HappyPants
+1  A: 
T.K.