Skip to content
/ BSTGo Public

This is a Go implementation of the BST data structure with a few of the most common operations. The algorithms code should be easy to understand. BST Tree is a binary tree in which the value of each node is greater than or equal to any value stored in the left sub-tree, and less than or equal to any value stored in the right sub-tree.

License

Notifications You must be signed in to change notification settings

BaseMax/BSTGo

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

19 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

BST Go

This is a Go implementation of the BST data structure with a few of the most common operations. The algorithms code should be easy to understand. BST Tree is a binary tree in which the value of each node is greater than or equal to any value stored in the left sub-tree, and less than or equal to any value stored in the right sub-tree.

Structure

Types:

type Node struct {
	value int
	left  *Node
	right *Node
}

type BST struct {
	root *Node
}

Functions:

  • func insert(root *Node, value int) *Node: Insert a new node into the BST.
  • func insertNonRecursively(root *Node, value int) *Node: Insert a new node into the BST (non-recursively).
  • func find(root *Node, value int) *Node: Find the node with the given value.
  • func findNonRecursively(root *Node, value int) *Node: Find the node with the given value (non-recursively).
  • func findLeftMost(root *Node) *Node: Find the left most child of the given node.
  • `func findParent(root *Node, value int) *Node: Find the parent of the given node.
  • func findFirstParent(root *Node) *Node: Find the first parent of the given node which is the left child of its parent.
  • func findNext(root *Node, value int) *Node: Find next of the given node.
  • func findNextAny(root *Node, node *Node) *Node: Find next of the given node (for any Binary Tree).
  • func deleteNode(root *Node, value int) *Node: Delete a node with the given value.
  • func deleteNodeNonRecursively(root *Node, value int) *Node: Delete a node with the given value (non-recursive).
  • func getHeight(root *Node) int: Get the height of the BST.
  • func getHeightNonRecursive(root *Node) int: Get the height of the BST (non-recursively).
  • func max(a, b int) int: Get the maximum of two integers.
  • func getSize(root *Node) int: Get the size of the BST.
  • func getSizeNonRecursive(root *Node) int: Get the size of the BST (non-recursively).

Example

// Create a BST
bst := BST{}

// Insert nodes into the BST
bst.root = insert(bst.root, 5)
bst.root = insert(bst.root, 3)
bst.root = insert(bst.root, 7)
bst.root = insert(bst.root, 2)
bst.root = insert(bst.root, 4)
bst.root = insert(bst.root, 6)
bst.root = insert(bst.root, 8)

// insertNonRecursively
bst.root = insertNonRecursively(bst.root, 15)
bst.root = insertNonRecursively(bst.root, 13)
bst.root = insertNonRecursively(bst.root, 17)
bst.root = insertNonRecursively(bst.root, 12)
bst.root = insertNonRecursively(bst.root, 14)

// Find the node with the given value
n := findNext(bst.root, 5)
if n != nil {
    println(n.value)
}

// Find a node
n = find(bst.root, 5)
if n != nil {
    println(n.value)
}

// findNonRecursively
n = findNonRecursively(bst.root, 5)
if n != nil {
    println(n.value)
}

// Get the height
println(getHeight(bst.root))

Copyright (c) 2022, Max Base

About

This is a Go implementation of the BST data structure with a few of the most common operations. The algorithms code should be easy to understand. BST Tree is a binary tree in which the value of each node is greater than or equal to any value stored in the left sub-tree, and less than or equal to any value stored in the right sub-tree.

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages