bstree.go

// Binary search tree.
//
// For more details check out those links below here:
// Wikipedia article: https://en.wikipedia.org/wiki/Binary_search_tree
// see bstree.go

package tree

import "github.com/TheAlgorithms/Go/constraints"

// Verify Interface Compliance
var _ Node[int] = &BSNode[int]{}

// BSNode represents a single node in the BinarySearch.
type BSNode[T constraints.Ordered] struct {
	key    T
	parent *BSNode[T]
	left   *BSNode[T]
	right  *BSNode[T]
}

func (n *BSNode[T]) Key() T {
	return n.key
}

func (n *BSNode[T]) Parent() Node[T] {
	return n.parent
}

func (n *BSNode[T]) Left() Node[T] {
	return n.left
}

func (n *BSNode[T]) Right() Node[T] {
	return n.right
}

// BinarySearch represents a Binary-Search tree.
// By default, _NIL = nil.
type BinarySearch[T constraints.Ordered] struct {
	Root *BSNode[T]
	_NIL *BSNode[T] // a sentinel value for nil
}

// NewBinarySearch creates a novel Binary-Search tree
func NewBinarySearch[T constraints.Ordered]() *BinarySearch[T] {
	return &BinarySearch[T]{
		Root: nil,
		_NIL: nil,
	}
}

// Empty determines the Binary-Search tree is empty
func (t *BinarySearch[T]) Empty() bool {
	return t.Root == t._NIL
}

// Push a chain of Node's into the BinarySearch
func (t *BinarySearch[T]) Push(keys ...T) {
	for _, key := range keys {
		t.pushHelper(t.Root, key)
	}
}

// Delete removes the node of val
func (t *BinarySearch[T]) Delete(val T) bool {
	node, ok := t.Get(val)
	if !ok {
		return false
	}
	t.deleteHelper(node.(*BSNode[T]))
	return true
}

// Get a Node from the Binary-Search Tree
func (t *BinarySearch[T]) Get(key T) (Node[T], bool) {
	return searchTreeHelper[T](t.Root, t._NIL, key)
}

// Has Determines the tree has the node of Key
func (t *BinarySearch[T]) Has(key T) bool {
	_, ok := searchTreeHelper[T](t.Root, t._NIL, key)
	return ok
}

// PreOrder Traverses the tree in the following order Root --> Left --> Right
func (t *BinarySearch[T]) PreOrder() []T {
	traversal := make([]T, 0)
	preOrderRecursive[T](t.Root, t._NIL, &traversal)
	return traversal
}

// InOrder Traverses the tree in the following order Left --> Root --> Right
func (t *BinarySearch[T]) InOrder() []T {
	return inOrderHelper[T](t.Root, t._NIL)
}

// PostOrder traverses the tree in the following order Left --> Right --> Root
func (t *BinarySearch[T]) PostOrder() []T {
	traversal := make([]T, 0)
	postOrderRecursive[T](t.Root, t._NIL, &traversal)
	return traversal
}

// LevelOrder returns the level order traversal of the tree
func (t *BinarySearch[T]) LevelOrder() []T {
	traversal := make([]T, 0)
	levelOrderHelper[T](t.Root, t._NIL, &traversal)
	return traversal
}

// AccessNodesByLayer accesses nodes layer by layer (2-D array),  instead of printing the results as 1-D array.
func (t *BinarySearch[T]) AccessNodesByLayer() [][]T {
	return accessNodeByLayerHelper[T](t.Root, t._NIL)
}

// Depth returns the calculated depth of a binary search tree
func (t *BinarySearch[T]) Depth() int {
	return calculateDepth[T](t.Root, t._NIL, 0)
}

// Max returns the Max value of the tree
func (t *BinarySearch[T]) Max() (T, bool) {
	ret := maximum[T](t.Root, t._NIL)
	if ret == t._NIL {
		var dft T
		return dft, false
	}
	return ret.Key(), true
}

// Min returns the Min value of the tree
func (t *BinarySearch[T]) Min() (T, bool) {
	ret := minimum[T](t.Root, t._NIL)
	if ret == t._NIL {
		var dft T
		return dft, false
	}
	return ret.Key(), true
}

// Predecessor returns the Predecessor of the node of Key
// if there is no predecessor, return default value of type T and false
// otherwise return the Key of predecessor and true
func (t *BinarySearch[T]) Predecessor(key T) (T, bool) {
	node, ok := searchTreeHelper[T](t.Root, t._NIL, key)
	if !ok {
		var dft T
		return dft, ok
	}
	return predecessorHelper[T](node, t._NIL)
}

// Successor returns the Successor of the node of Key
// if there is no successor, return default value of type T and false
// otherwise return the Key of successor and true
func (t *BinarySearch[T]) Successor(key T) (T, bool) {
	node, ok := searchTreeHelper[T](t.Root, t._NIL, key)
	if !ok {
		var dft T
		return dft, ok
	}
	return successorHelper[T](node, t._NIL)
}

func (t *BinarySearch[T]) pushHelper(x *BSNode[T], val T) {
	y := t._NIL
	for x != t._NIL {
		y = x
		switch {
		case val < x.Key():
			x = x.left
		case val > x.Key():
			x = x.right
		default:
			return
		}
	}

	z := &BSNode[T]{
		key:    val,
		left:   t._NIL,
		right:  t._NIL,
		parent: y,
	}
	if y == t._NIL {
		t.Root = z
	} else if val < y.key {
		y.left = z
	} else {
		y.right = z
	}
}

func (t *BinarySearch[T]) deleteHelper(z *BSNode[T]) {
	switch {
	case z.left == t._NIL:
		t.transplant(z, z.right)
	case z.right == t._NIL:
		t.transplant(z, z.left)
	default:
		y := minimum[T](z.right, t._NIL).(*BSNode[T])
		if y.parent != z {
			t.transplant(y, y.right)
			y.right = z.right
			y.right.parent = y
		}

		t.transplant(z, y)
		y.left = z.left
		y.left.parent = y
	}
}

func (t *BinarySearch[T]) transplant(u, v *BSNode[T]) {
	switch {
	case u.parent == t._NIL:
		t.Root = v
	case u == u.parent.left:
		u.parent.left = v
	default:
		u.parent.right = v
	}

	if v != t._NIL {
		v.parent = u.parent
	}
}