CODEWITHSUNDEEP
pointersstructtreegotree-traversal
Francis
Francis

Reputation: 949

Go tree traversal, trying to understand the code

I'm looking at this page on Rosettacode.org about tree traversal. I'm looking at the Go implementation, I'm fairly new to Go which is why I'd like your help.

Right at the beginning of the file, a struct is created. That's ok it makes sense so far. But the thing I don't understand is this:

type node struct {
    value       int
    left, right *node
}

The left, right *node part. I understand that the left, right variables are of type pointer to node. But I don't understand why, first-off I didn't know you could include the type you are creating, in this case node in the actual struct itself. And then I don't really understand why the code doesn't just say left, right node.

func (n *node) iterPreorder(visit func(int)) {
    if n == nil {
        return
    }
    visit(n.value)
    n.left.iterPreorder(visit)
    n.right.iterPreorder(visit)
}

The next thing I don't get is, how the visit variable can be of type func(int). Then I also don't get how you can use iterPreorder within the function iterPreorder.

And finally I'd just like to ask, what does this code do?

tree := &node{1,
    &node{2,
        &node{4,
            &node{7, nil, nil},
            nil},
        &node{5, nil, nil}},
    &node{3,
        &node{6,
            &node{8, nil, nil},
            &node{9, nil, nil}},
        nil}}

Thanks, here's a link to the full code over on Rosettacode.org.

Upvotes: 3

Views: 475

Answers (1)

OneOfOne
OneOfOne

Reputation: 99224

Let's take it step by step.

  1. It uses pointers because left and/or right can be nil (not set at all), you can't have that with a value. Also if they used left, right node you would have an infiniate number of nodes since that value will always be set.

  2. visit func(int) allows you to pass a function of the type func(int), like callbacks in other languages.

  3. n.left.iterPreorder / n.right.iterPreorder, you're actually calling iterPreorder on a child node, not the same node it got called from.

  4. The code simply creates a tree and assigns it's nodes.

To visualize it better:

tree := &node{1,
    &node{2,
        &node{4,
            &node{7, nil, nil},
            nil},
        &node{5, nil, nil}},
    &node{3,
        &node{6,
            &node{8, nil, nil},
            &node{9, nil, nil}},
        nil}}

Is the same as:

tree = &node{value: 1}
tree.left = &node{value:2}
tree.left.left = &node{value: 4}
tree.left.left.left = &node{value: 7}
tree.left.right = &node{value: 5}

tree.right = &node{value:3}
tree.right.left = &node{value: 6}
tree.right.left.left = &node{value: 8}
tree.right.left.right = &node{value: 9}

bonus:

  • Using & returns a pointer, for example n := &node{}, n is a pointer to a node.

Check this excellent article about Go pointers.

Also Effective Go is a must a read, and try going through the tour

Upvotes: 6

Related Questions