3 Replies Latest reply: Aug 20, 2010 6:35 AM by 800282 RSS

    Recursive method for traversing a tree structure.

    843853
      Hello!

      I am wondering if anybody could show me an example of how to write a recursive method for traversing a
      tree and all its sub nodes.
      And i would also want to see different ways to do it.
      And i would also want to know the most effective way to do it.

      Thank you.
        • 1. Re: Recursive method for traversing a tree structure.
          800282
          I am wondering if anybody could show me an example of how to write a recursive method for traversing a
          tree and all its sub nodes.
          tree {
            
            node root
          
            traverse() {
              traverse(root)
            }
          
            traverse(node) {
              if(node is not null) {
                traverse(node.left) // recursive call
                traverse(node.right) // recursive call
              }
            }
          }
          And i would also want to see different ways to do it.
          What do you mean?
          And i would also want to know the most effective way to do it.
          How can traversing all nodes in a tree be done more efficient? I mean, you have to do them all. Doing it more efficient would be to stop half-way, but then you're not traversing them all... Can you elaborate?
          • 2. Re: Recursive method for traversing a tree structure.
            843853
            I am not so good at writing this kind of algorithms. So i thought there might be different algorithms for doing that.
            But now i know that there is only one way to do it. Thanks for your answer.
            • 3. Re: Recursive method for traversing a tree structure.
              800282
              mattias_westerberg wrote:
              I am not so good at writing this kind of algorithms. So i thought there might be different algorithms for doing that.
              But now i know that there is only one way to do it. Thanks for your answer.
              No problem.
              There are different ways to walk through a tree, perhaps that is what you mean? Have a look at this Wiki article that explains them: [http://en.wikipedia.org/wiki/Tree_traversal]