Version: v0.0.0-...-241115c Latest Latest Go to latest
Published: Aug 25, 2021 License: MIT

## Documentation ¶

### Overview ¶

Package bst is an implementation for binary search tree data structure in go language

### Constants ¶

This section is empty.

### Variables ¶

This section is empty.

### Functions ¶

This section is empty.

### Types ¶

#### type Node ¶

```type Node struct {
Data  int
Left  *Node
Right *Node
}```

Node struct contains actual data and address to left and right node

#### func NewNode ¶

`func NewNode(data int) *Node`

NewNode creates a new Node with integer data

#### type Tree ¶

```type Tree struct {
Root *Node
}```

Tree struct contains the pointer to root node

#### func NewBST ¶

`func NewBST() *Tree`

NewBST creates an empty BST Tree

#### func (*Tree) Delete ¶

`func (t *Tree) Delete(data int) error`

Delete deletes a node with said data such that the binary search tree property is still maintained.

The main problem with BST deletion (Hibbard Deletion) is that it is not symmetric. After many insertion and deletion BST become less balance. Researchers proved that after sufficiently long number of random insert and delete height of the tree becomes sqrt(n) . so now every operation (search, insert, delete) will take sqrt(n) time which is not good compare to O(logn).

#### func (*Tree) Find ¶

`func (t *Tree) Find(data int) bool`

Find returns true if integer is present in the binary search tree, else false.

#### func (*Tree) FindMax ¶

`func (t *Tree) FindMax() (int, error)`

FindMax returns the max element from the dataset

#### func (*Tree) FindMin ¶

`func (t *Tree) FindMin() (int, error)`

FindMin returns the max element from the dataset

#### func (*Tree) Height ¶

`func (t *Tree) Height() int`

Height returns the height of the tree

#### func (*Tree) InOrder ¶

`func (t *Tree) InOrder(node *Node, printFunction func(*Node))`

InOrder traverses the tree in inorder fashion

```Inorder Algorithm

Visit all the nodes in the left subtree
Visit the root node
Visit all the nodes in the right subtree
```

#### func (*Tree) Insert ¶

`func (t *Tree) Insert(data int) error`

Insert inserts new integer data into the tree at the position, so that the binary search tree property is maintained.

#### func (*Tree) IsBST ¶

`func (t *Tree) IsBST() bool`

IsBST returns true if the existing binary tree is a binary search tree, else false.

#### func (*Tree) LevelOrder ¶

`func (t *Tree) LevelOrder()`

LevelOrder traversal of a tree is breadth first traversal for the tree

```Example:

F
/	  \
B     G
/   \    \
A      D    I

Level Order Traversal := F -> B -> G -> A -> D -> I
```

#### func (*Tree) PostOrder ¶

`func (t *Tree) PostOrder(node *Node, printFunction func(*Node))`

PostOrder traverses the tree in inorder fashion

```Postorder Algorithm

Visit all the nodes in the left subtree
Visit all the nodes in the right subtree
Visit the root node
```

#### func (*Tree) PreOrder ¶

`func (t *Tree) PreOrder(node *Node, printFunction func(*Node))`

PreOrder traverses the tree in inorder fashion

```Preorder Algorithm

Visit the root node
Visit all the nodes in the left subtree
Visit all the nodes in the right subtree
```