# Maximum element between two nodes of BST in golang

Go program for Maximum element between two nodes of BST. Here mentioned other language solution.

``````package main
import "fmt"
// Go program for
// Detect max nodes between given two nodes of a BST

// Binary Search Tree Node
type TreeNode struct {
// Data value
data int
// Indicates left and right subtree
left * TreeNode
right * TreeNode
}
func getTreeNode(data int) * TreeNode {
// return new TreeNode
return &TreeNode {
data,
nil,
nil,
}
}
type BinarySearchTree struct {
root * TreeNode
}
func getBinarySearchTree() * BinarySearchTree {
// return new BinarySearchTree
return &BinarySearchTree {
nil,
}
}
// Insert a new node in BST
// Create a dynamic node of binary search tree
var node * TreeNode = getTreeNode(value)
if this.root == nil {
// When adds a first node in binary tree
this.root = node
} else {
var find * TreeNode = this.root
// Add new node to proper position
for (find != nil) {
if find.data >= value {
if find.left == nil {
find.left = node
return
} else {
// Visit left sub-tree
find = find.left
}
} else {
if find.right == nil {
find.right = node
return
} else {
// Visit right sub-tree
find = find.right
}
}
}
}
}
func(this BinarySearchTree) findNode(node * TreeNode,
value int) * TreeNode {
if node != nil {
if node.data > value {
// Find node in left subtree
return this.findNode(node.left, value)
} else if node.data < value {
// Find node in right subtree
return this.findNode(node.right, value)
} else {
// When node exist
return node
}
}
// When node is not exist
return nil
}
// Find LCA of two BST nodes
func(this BinarySearchTree) lca(node * TreeNode,
first int, second int) * TreeNode {
if node != nil {
if node.data > first && node.data > second {
return this.lca(node.left, first, second)
} else if node.data < first && node.data < second {
return this.lca(node.right, first, second)
}
return node
}
return nil
}
func(this BinarySearchTree) findMaxBetween(first, second int) {
if this.root != nil {
// First we are check that given node are exist or not in BST
if this.findNode(this.root, first) != nil &&
this.findNode(this.root, second) != nil {
// If given element is exist then get LCA
var node * TreeNode = this.lca(this.root, first, second)
var find int = first
if first < second {
find = second
}
var result int = find
// node is lca of both node (x,y)
// so we consider path from node of largest of (x,y)
// And find max node of this path
for (node != nil) {
if node.data > result {
result = node.data
}
if node.data > find {
// Visit to left child
node = node.left
} else if node.data < find {
// Visit to right child
node = node.right
} else {
break
}
}
fmt.Println("Max Node Between [", first, ",",
second, "] is ", result)
} else {
fmt.Println("Node [", first, ",",
second, "] are missing")
}
} else {
fmt.Println("\nEmpty BST")
}
}
func main() {
var tree * BinarySearchTree = getBinarySearchTree()
// Binary search tree
/*
10
/ \
/   \
/     \
3      19
/ \    /  \
1   4  14  50
/ \
-3   2

*/
// Testing
tree.findMaxBetween(2, 14)
tree.findMaxBetween(-3, 4)
tree.findMaxBetween(10, 2)
tree.findMaxBetween(3, 2)
}``````

Output

``````Max Node Between [2,14] is 19
Max Node Between [-3,4] is 4
Max Node Between [10,2] is 10
Max Node Between [3,2] is 3``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.