Talk:Tree traversal

From Wikipedia, the free encyclopedia

1 Uncategorized
2 iterative in order traversal
3 Duplicate node rehash
4 Black box image
5 Iterative traversal Redux
6 Animation?
7 Flaws in all of these algorithms
8 Rewrite
9 RPN
10 Changes on 14 Feb 07
11 Start of article
12 Removed wikify tag
13 Problem with iterative solution

[edit] Uncategorized

err geeks —The preceding unsigned comment was added by 212.219.204.70 (talk • contribs) 24 November 2004.

The diagram might be a bit better if each element was distinct. It's a bit confusing when some of the elements are identical (why is there more than one 5?) —The preceding unsigned comment was added by 68.0.167.91 (talk • contribs) 8 February 2005.

I agree this is not a good example. 2 is another duplicate. Use letters instead:

—The preceding unsigned comment was added by 172.148.71.47 (talk • contribs) 31 August 2005.

[edit] iterative in order traversal

algorithm requires a check if a node has been already printed other wise it will always keep on printing the leftmost and its parent. —The preceding unsigned comment was added by 66.235.10.126 (talk • contribs) 30 December 2005.

Thanks! When doing the recursive to iterative translation I forgot to keep in mind that we somehow have to remember the code position at the last call. I'll ponder how to do this in a neat clean way. Deco 10:59, 30 December 2005 (UTC)

This is what I came up with in C/C++

   void inorder(node* root) {
     bool done = false;
     Stack<node*> stack;
     node* current = root;
     while (!done)
     {
       if (current)
       {
           stack.push(current);
           current = current->left;
        }
       else
       {
            if ( stack.empty() == false)
            {
              current = stack.pop();
              cout << current->value;
              current = current->right;
             }
             else 
                   done = true;
       }
     }
   }

—The preceding unsigned comment was added by 131.107.0.106 (talk • contribs) 31 December 2005.

[edit] Duplicate node rehash

Another anon seems to think that duplicated nodes in the example is confusing. Is there any way we can fix this? — Ambush Commander^(Talk) 03:18, 26 February 2006 (UTC)

User:R. S. Shaw took care of it on March 16, 2006: see this edit. --ZeroOne 15:11, 21 March 2006 (UTC)

[edit] Black box image

The image on this page, Binary_tree_(letters).png, appears to be just a black box on my computer. Does anyone else have this problem?--GregRM 04:00, 20 May 2006 (UTC)

[edit] Iterative traversal Redux

The currently presented iterative algorithm I find a little too obscure. For reference, here it is:

visit(root) {
    prev    := null
    current := root
    next    := null
   
    while current ≠ null {
        if prev == current.parent
            prev := current
            next := current.left
        if next == null or prev == current.left
            print current.value
            prev := current
            next := current.right
        if next == null or prev == current.right
            prev := current
            next := current.parent
        current := next
    }
}

For a few days, the following version was in the article:

visit(root) {
    prev    := null
    current := root
    next    := null
   
    while current ≠ null {
        if prev == current.parent
            next := current.left
        if next == null or prev == current.left
            print current.value
            next := current.right
        if next == null or prev == current.right
            next := current.parent
        prev := current
        current := next
    }
}

It's a little simpler because the "prev := current" has been factored out. But it doesn't work in some cases because of subtleties in the code. It's not a simple factoring because in the original the "prev := current" affected the if statements which followed it, which the factored version does not. Only occasionally does that matter.

One case it fails for is where the root has only one child, a left-hand child. After taking the first then clause ("next := current.left") it mistakenly executes the third then clause ("next := current.parent") causing next to be set to null and the loop to be exited. This is because the test "prev == current.right" succeeds since both values are null. In the original/current code, this failure was prevented by the earlier execution of "prev := current".

I think the current algorithm is too subtle to be a good example. I'm looking at modifications to clarify it. -R. S. Shaw 03:27, 9 June 2006 (UTC)

Ah, I see. I didn't take into account the fact that the flow of execution fell through to the next if statement. Al 03:44, 9 June 2006 (UTC)

I agree. I wrote it. If you can come up with anything simpler that would be great. Deco 09:10, 9 June 2006 (UTC)

After looking at some alternatives, I've put in a new version of the algorithm. This one uses a nested subroutine (for something that could have just been duplicate code) because it seemed a little clearer despite the extra routine. -R. S. Shaw 00:17, 10 June 2006 (UTC)

Personally I find that more complicated, since "midvisit" doesn't seem to have a clear conceptual role. Maybe I'm missing something. Deco 01:20, 10 June 2006 (UTC)

[edit] Animation?

Illustrating the various traversal schemes with some animations would be a great help I think. --72.255.5.82 04:24, 16 August 2006 (UTC)

[edit] Flaws in all of these algorithms

I notice that all of the algorithms that I looked at on this page contain at least one major bug: They will fail if they are initially passed an empty tree. There is a better way to write them, that avoids this bug (or obligation on the caller if you prefer) and is just as efficient. For example, the preorder traversal could be written (using the same style):

 visit(node)
     if (node == null) return
     print node.value
     visit(node.left)
     visit(node.right)

While this makes twice as many calls to "visit", it also avoids half the dereferences to node's children, so that's arguably a performance wash (it depends on the circumstances as to which will truly run faster). And it eliminates the major bug. All of these code examples can and should be rewritten in the same way.

I think it would also be clearer to call the functions "preorder" "postorder" and "inorder," respectively, instead of calling them all "visit." Cliff Shaffer, 10:25, 21 September 2006.

[edit] Rewrite

I rewrote the article, removing implementations, as they were probably incorrect, according to the various comments on them, and as implementations don't replace a good explanation. I consider the article to be a stub now, and valid and clean implementations could be added (I plan to). I also didn't keep the external links, that were not even really related to tree traversal, but merely to the use of graphs in the context of database, and probably came from a web development background (PHP and MySQL related links).

There are surely far better and more classic references to the subject, but the O'Reilly book is the one where I learned tree traversal and where I verified my stub. In particular, I suspect there is a treatment of trees and corresponding algorithms in The Art of Computer Programming, but I don't have it at hand.

Nowhere man 22:15, 1 December 2006 (UTC)

[edit] RPN

The reverse polish notation used in HP calculators is the postfix, not the prefix notation. I don't know English enough to rewrite...

[edit] Changes on 14 Feb 07

To anyone watching this article, let me know what you think of the modifications. Restructured it quite a bit, no doubt slipped some typos/mistakes in, but I tried to make it look a bit more professional.

Also changed all the pseudocode to be consistent with one another (some were using curly braces to mark blocks, others just used whitespace - I started at the top where there was whitespace delimited blocks, and made the rest like that), and completely changed the algorithm for iterative/explicit stack based traversals. Let me know if I stuffed it up ! The original code definitely works, but it's possible I mucked up the pseudocode translation. Benefit of the new pseudocode is that at any point the direction could be changed (just use rights instead of lefts, lefts instead of rights), even mid traversal... and that the stack based implementation is virtually identical to the parent pointers implementation.

Also added an example for how to in-order traverse a threaded tree.

Phew. Over an hour down the drain, hope somebody finds it useful =P Themania 06:24, 28 February 2007 (UTC)

It looks great. I'll be reviewing it for stylistic concerns, but that's a lot of useful information you've added in. — Edward Z. Yang^(Talk) 22:48, 28 February 2007 (UTC)

Thanks Edward =) apologies about reverting your revert - I'm pretty confident that the anomynous ip-logged user was correct, although reverting reverts should probably be mentioned on the talk page..? —The preceding unsigned comment was added by Themania (talk • contribs) 00:11, 1 March 2007 (UTC).

No, it's okay. It's tough to tell whether or not an edit is legit when there's no edit summary given. — Edward Z. Yang^(Talk) 02:29, 1 March 2007 (UTC)

Would be, especially for non user edits. Just reassuring to know that there's people watching =) Themania 15:15, 1 March 2007 (UTC)

[edit] Start of article

"In computer science, tree traversal refers to the process of visiting each node in a non-linear data structure (eg: Tree, Graph...)"

Errm, no. 'tree traversal' is traversing a tree. Traversing a more general graph is called, oddly enough, 'graph traversal'. —The preceding unsigned comment was added by 131.111.85.79 (talk) 11:09, 8 March 2007 (UTC).

[edit] Removed wikify tag

I removed the wikify tag, although I'm not sure of the process that I should have gone through before removing it. All I did was compare the version that had the wikify tag added, and the current version - the article is very different. Possibly the introduction should be longer, although don't know what else to add ^^

Also fixed the statement reported by 131.111.85.79, and a few minor wording changes. Hopefully for the better, although a lil dubious. Themania 15:21, 8 March 2007 (UTC)

[edit] Problem with iterative solution

inorder(node)

while hasleftchild(node) do
  node = node.left
do
  visit(node)
  if not (hasrightchild(node)) then
    node = node.right // <------------------ look here
  else
    node = node.right // <------------------ and here
  while hasleftchild(node) do
    node = node.left
while node ≠ null

This can't be right...

Philfreo 18:59, 23 March 2007 (UTC)

You're right, it's wrong. The inner while should have been under the then. I've fixed the article. Note that this is not just some iterative solution, it is only for a threaded tree, which essentially always has pointers to skip directly to the next inorder node from a node without a right child, so it happens to have a very simple inorder walk because of the extra threading. -R. S. Shaw 03:31, 24 March 2007 (UTC)

Retrieved from "http://en.wikipedia.org../../../t/r/e/Talk%7ETree_traversal_cc81.html"