<p>I am trying to learn data structures using Go and to be a better programmer in general. </p>
<p>I was curious why some implementation of Binary Search Tree have root node in the struct and some don't.</p>
<p>I like this blog post, <a href="http://tobin.cc/blog/bst/" rel="nofollow">http://tobin.cc/blog/bst/</a> where he declares it like this</p>
<pre><code>type Node struct {
key *int
Left, Right,Root *Node
}
</code></pre>
<p>then he places all the nodes in a tree object</p>
<pre><code>type Tree struct {
root *Node
}
</code></pre>
<p>I seen implementations where there is no root node in Node struct and some implementations of no tree object whatsoever.</p>
<p>What is a good implementation to study? A simple implementation without interfaces is preferred. And int type is fine with me.</p>
<hr/>**评论：**<br/><br/>pekim: <pre><blockquote>
<p>I was curious why some implementation of Binary Search Tree have root node in the struct and some don't.</p>
</blockquote>
<p>It's likely so that receiver functions can be used with the struct. This is an example of that in the blog article that you referenced.</p>
<pre><code>func (t *Tree) Flatten() []int {
...
}
</code></pre></pre>joh_ng: <pre><p>As for me, i prefer the declaration of the node without root. The node added first is the root of the BST.
The implementation below is done in C++</p>
<p>struct Node
{
int key;
Node* left, right;</p>
<p>Node(int _key) : key(_key), left(nullptr), right(nullptr) {}
};</p>
<p>Node* insert(Node* currentNode, int newKey)
{
if (currentNode == nullptr) return new Node(newKey);
else
{
If (newKey <= currentNode->key) currentNode->left = insert(currentNode->left, newKey);
else currentNode->right = insert(currentNode->right, newKey);
}
return currentNode;
}</p>
<p>void main()
{
/* Assuming wanna construct a simple BST as below
4
/ \
2 6</p>
<p>Node with key value is 4 is root
<em>/
Node</em> currentNode = insert(4);
Node* root = currentNode; // the root node of BST</p>
<p>currentNode = insert(currentNode, 2);
currentNode = insert(currentNode, 6);
}</p></pre>joh_ng: <pre><p>Oh, why auto cut off few asterisk symbol like Node* (currentNode, int newKey)</p></pre>
