bst_construction

README

BST Construction

Write a BST class for a Binary Search Tree. The class should support:

• Inserting values with the insert method.
• Removing values with the remove method; this method should only remove the first instance of a given value.
• Searching for values with the contains method.

Note that you can't remove values from a single-node tree. In other words, calling the remove method on a single-node tree should simply not do anything.

Each BST node has an integer value, a left child node, and a right child node. A node is said to be a valid BST node if and only if it satisfies the BST property: its value is strictly greater than the values of every node to its left; its value is less than or equal to the values of every node to its right; and its children nodes are either valid BST nodes themselves or None / null.

Sample Usage

// Assume the following BST has already been created:
         10
       /     \
      5      15
    /   \   /   \
   2     5 13   22
 /           \
1            14

// All operations below are performed sequentially.
insert(12):   10
            /     \
           5      15
         /   \   /   \
        2     5 13   22
      /        /  \
     1        12  14

remove(10):   12
            /     \
           5      15
         /   \   /   \
        2     5 13   22
      /           \
     1            14

contains(15): true

Hints

Hint 1
As you try to insert, find, or a remove a value into, in, or from a BST, you will have to traverse the tree's nodes. The BST property allows you to eliminate half of the remaining tree at each node that you traverse: if the target value is strictly smaller than a node's value, then it must be (or can only be) located to the left of the node, otherwise it must be (or can only be) to the right of that node.

Hint 2
Traverse the BST all the while applying the logic described in Hint #1. For insertion, add the target value to the BST once you reach a leaf (None / null) node. For searching, if you reach a leaf node without having found the target value that means the value isn't in the BST. For removal, consider the various cases that you might encounter: the node you need to remove might have two children nodes, one, or none; it might also be the root node; make sure to account for all of these cases.

Hint 3
What are the advantages and disadvantages of implementing these methods iteratively as opposed to recursively?

Optimal Space & Time Complexity
Average (all 3 methods): O(log(n)) time | O(1) space - where n is the number of nodes in the BST Worst (all 3 methods): O(n) time | O(1) space - where n is the number of nodes in the BST

Documentation

Index

• type BST
  • func NewBST(value int) *BST
  • func (tree *BST) Contains(value int) bool
  • func (tree *BST) Contains1(value int) bool
  • func (tree *BST) DFS(level int, arr *[]int)
  • func (tree *BST) Depth() int
  • func (tree *BST) Height() int
  • func (tree *BST) IDDFS() []int
  • func (tree *BST) Insert(value int) *BST
  • func (tree *BST) Insert1(value int) *BST
  • func (tree *BST) Rank(value int) int
  • func (tree *BST) Remove(value int) *BST
  • func (tree *BST) Remove1(value int) *BST
  • func (tree *BST) Remove2(value int) *BST

Types

type BST

type BST struct {
	Value, Size int

	Left  *BST
	Right *BST
}

func NewBST

func NewBST(value int) *BST

func (*BST) Contains

func (tree *BST) Contains(value int) bool

Contains Better solution

func (*BST) Contains1

func (tree *BST) Contains1(value int) bool

func (*BST) DFS

func (tree *BST) DFS(level int, arr *[]int)

func (*BST) Depth

func (tree *BST) Depth() int

func (*BST) Height

func (tree *BST) Height() int

func (*BST) IDDFS

func (tree *BST) IDDFS() []int

IDDFS https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search

func (*BST) Insert

func (tree *BST) Insert(value int) *BST

Insert Better solution

func (*BST) Insert1

func (tree *BST) Insert1(value int) *BST

Insert1 Better solution1

func (*BST) Rank

func (tree *BST) Rank(value int) int

func (*BST) Remove

func (tree *BST) Remove(value int) *BST

func (*BST) Remove1

func (tree *BST) Remove1(value int) *BST

Remove1 Better solution

func (*BST) Remove2

func (tree *BST) Remove2(value int) *BST