bintree

[christophberger]

Written on 02/25/2017 20:54:07

URL: https://appliedgo.net/bintree/

[christophberger]

Migrated comment, written by joonas_fi on 02/27/2017 07:49:22

Awesome visualizations!

[christophberger]

Migrated comment, written by Christoph on 02/27/2017 09:12:58

Thanks! :)

[christophberger]

Migrated comment, written by 4asd1 on 06/18/2017 22:17:04

An example binary search tree package https://github.com/4d553975...
GoDoc: https://godoc.org/github.co...

[christophberger]

Migrated comment, written by Hugues Alary on 02/04/2018 21:31:48

Thanks for the great post!

I have one question:
Taking the Insert() method: func (n *Node) Insert(value, data string) error
At the top of the method, you check that *n is not nil:

if n == nil {
return errors.New("Cannot insert a value into a nil tree")
}

isn't that case impossible? Since, to be able to insert a value into the tree *n, you had to declare n := &Node{} and by consequence, *n is not nil?

[christophberger]

Migrated comment, written by Christoph on 02/05/2018 08:43:45

Go allows to invoke methods even for the zero value of a type. (Which is effectively like invoking static methods in C++, Java, or C#.) For pointer types, the zero value is the nil pointer. Hence it is possible to write something like

var node *Node // node defaults to the zero value, that is, nil
node.Insert("a", "b")

and therefore, all methods of *Node need to check if the current node is nil. (I noticed I forgot to add this check to findMax() - that's fixed now.)

[christophberger]

Migrated comment, written by Hugues Alary on 02/05/2018 20:01:55

Makes total sense, thanks.

[Wojtek-ana]

The delete in this article doesn't work for removing root of a tree. You need something like: if fakeparent.right != t.root { t.root = fakeparent.right }

otherwise t.root continues to point to original root of the tree.

[christophberger]

Hi @Wojtek-ana, thanks for your input.

I cannot recreate the problem you describe. The following test passes:

func TestTree_Delete(t *testing.T) {
    type args struct {
        s string
    }
    tests := []struct {
        name       string
        tree, want Tree
        args       args
        wantErr    bool
    }{
        {
            name: "Delete root in root-only tree",
            tree: Tree{
                Root: &Node{
                    Value: "a",
                    Data:  "a",
                },
            },
            want: Tree{
                Root: nil,
            },
            args: args{
                s: "a",
            },
            wantErr: false,
        },
    }
    for _, tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            err := tt.tree.Delete(tt.args.s)
            if (err != nil) != tt.wantErr {
                t.Errorf("Tree.Delete() error = %v, wantErr %v", err, tt.wantErr)
            }
            if err == nil && !reflect.DeepEqual(tt.tree, tt.want) {
                t.Errorf("Tree.Delete() = %v, want %v", tt.tree, tt.want)
            }
        })
    }
}

Deleting the root node results in an empty tree (Root == nil). Can you share an example that leaves t.Root non-nil?