To find the largest Binary Search Tree (BST) in a binary tree we should be aware of the following terms:
Binary Tree:
A binary tree is defined as a tree with no more than two children. Each binary tree element can only have two children, we call them the left and right child.
Binary Search Tree:
A BST is a data structure that allows us to keep a sorted list of numbers in a short amount of time. A binary Search tree is also called a binary tree because each BST tree node has a maximum of two children. It is also called a search tree, because this can be used to search for the presence of a no. in logarithmic time. There are some properties that separate a normal binary tree from BST.
For instance,
All nodes of the left subtree are less than the root node in BST.
All the nodes on the right subtree are greater than the root node.
Inorder Traversal:
It signifies that after traversing the root node, the left subtree is visited first, followed by the right subtree. Inorder traversal refers to the process of traversing the root node between the left and right subtrees. As a result, each node in the inorder traversal gets visited in between its subtrees.
Prerequisite for this problem: To check if a tree is BST or not
Approach 1: Brute force
We must determine whether a node's left subtree contains any elements bigger than the node's value, as well as whether the node's right subtree contains any elements smaller than the node's value. We'll create two helper functions, getMin(root) and getMax(root), that return the tree's minimal and maximum values for a given root. Then we'll look at each node If the value of the node is greater than or equal to the maximum value in the left subtree Is the node's value less than or equal to the right subtree's minimum value?
We'll basically see if this expression is true or not: getMax(root.left)root.val
getMin(root.right).We are traversing and calling getMax(root.left) and getMin(root.right) for each node.We are traversing and calling getMax(root.left) and getMin(root.right) for each node hence it will cost quadratic time complexity.
Approach 2: Using Inorder Traversal
We know that traversing a binary search tree in an inorder way will result in sorted order of its elements. We'll take advantage of this by traversing the tree in reverse order and storing the elements in an array. The array will then be traversed in a linear fashion to see if it is in sorted order. Inorder traversal of BST for storing elements in arr[] + Single loop to check arr[] is sorted or not = O(n) + O(n) = O(n)
Now since we are aware of how to check if a subtree is a binary search tree or not then we can move with our main problem of finding the largest BST in binary tree search. So let’s explore all the different ways to solve this problem.
Comentários