Binary Search Tree (BST) is a data structure organized in such way that each node has comparable key and also satisfies condition that each key in the node is greater than any key in nodes of a left sub-tree and…