How do you perform a deep copy of a ternary tree in Go?

Question

I'm attempting to perform a deep copy of the following struct:

// Ternary Tree
type Tree struct {
    Left  *Tree
    Mid *Tree
    Right *Tree
    Value interface{}
    Parent *Tree
    Orientation string
    IsTerminal bool
    Type string
}

The following is my sorry attempt. It looks like I'm creating a new tree at the root but it's children are still pointing to the same address in memory.

func (tree *Tree) CopyTree() *Tree {
    if (tree == nil) {
        return nil
    } else {
        copiedTree := &Tree {
            tree.Left.CopyTree(),
            tree.Mid.CopyTree(),
            tree.Right.CopyTree(),
            tree.Value,
            tree.Parent.CopyTree(),
            tree.Orientation,
            tree.IsTerminal,
            tree.Type}
        return copiedTree
    }
}

Are there any useful constructs in go that assist with deep copying a struct? If not, how would I perform this deep copy myself? Note, the "deepcopy" package no longer works as it uses a few functions that were deprecated with the release of Go 1

There is nothing built in. There are, however, [packages such as DeepCopy that can do it for you](http://godoc.org/code.google.com/p/rog-go/exp/deepcopy) (keeping in mind the "experimental" status) — Simon Whitehead, Oct 27 '14 at 23:26
@SimonWhitehead I gave that package a try. Unfortunately, it uses a bunch of functions that were deprecated with the release of Go 1 — Adam Soffer, Oct 27 '14 at 23:33
Apologies .. I did not realise (I must have used it prior to Go 1). — Simon Whitehead, Oct 27 '14 at 23:35
Are you sure the code you give demonstrates the behavior you describe? There appears to be an infinite cycle where parent copies child copies parent. Also, you're not copying Value: is that intended? — Paul Hankin, Oct 27 '14 at 23:47
@Anonymous You were on point. I should have been assigning the copiedTree to the parent of of the Left, Right, and Mid children. I'll provide the correct code in an answer. Thanks for the direction. — Adam Soffer, Oct 28 '14 at 00:31

score 10 · Accepted Answer · edited Oct 29 '14 at 00:20

I was close. I should have assigned the copiedTree to the parent property.

func (tree *Tree) CopyTree() *Tree {
    if (tree == nil) {
        return nil
    } else {
        copiedTree := &Tree {
            tree.Left.CopyTree(),
            tree.Mid.CopyTree(),
            tree.Right.CopyTree(),
            tree.Value,
            nil,
            tree.Orientation,
            tree.IsTerminal,
            tree.Type,
        }

        if copiedTree.Left != nil {
            copiedTree.Left.Parent = copiedTree
        }
        if copiedTree.Right != nil {
            copiedTree.Right.Parent = copiedTree
        }
        if copiedTree.Mid != nil {
            copiedTree.Mid.Parent = copiedTree
        }
        return copiedTree
    }
}

score 0 · Answer 2 · answered Apr 18 '21 at 04:06

You can roundtrip it through encoding/gob:

package main

import (
   "bytes"
   "encoding/gob"
)

func copyStruct(in, out interface{}) {
   buf := new(bytes.Buffer)
   gob.NewEncoder(buf).Encode(in)
   gob.NewDecoder(buf).Decode(out)
}

func main() {
   type date struct { Month, Day int }
   a := date{12, 31}
   var b date
   copyStruct(a, &b)
}

https://golang.org/pkg/encoding/gob

score -1 · Answer 3 · answered Aug 05 '19 at 05:19

-1

How about json.Marshal and json.Unmarshal. If performance is critical, I perfer to use protobuf.

answered Aug 05 '19 at 05:19

g10guang

4,647
3
28
22

How do you perform a deep copy of a ternary tree in Go?

3 Answers3

Linked