day93

Documentation

Index

• Constants
• func SizeOfLargestBST(tree *BinaryTree) int
• type BinaryTree
  • func FindLargestBST(tree *BinaryTree) *BinaryTree
• type TreeInfo

Constants

const MaxInt = int(^uint(0) >> 1)

MaxInt is the largest int.

const MinInt = -MaxInt - 1

MinInt is the smallest int.

Functions

func SizeOfLargestBST

func SizeOfLargestBST(tree *BinaryTree) int

SizeOfLargestBST will return the number of nodes in the largest BST in the binary tree. Runs in O(N) time with no extra space.

Types

type BinaryTree

type BinaryTree struct {
	Value       int
	Left, Right *BinaryTree
}

BinaryTree is a binary tree: left & right children.

func FindLargestBST

func FindLargestBST(tree *BinaryTree) *BinaryTree

FindLargestBST will return a pointer to the root of the largest BST in the binary tree. Runs in O(N) time with no extra space.

type TreeInfo

type TreeInfo struct {
	IsBST  bool
	Min    int
	Max    int
	Size   int
	Ans    int
	AnsPtr *BinaryTree
}

TreeInfo contains information from a given subtree.