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.
To find the largest 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 binary search tree 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 number in logarithmic time.
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.
Commentaires