Largest BST in Binary Tree
Advanced Problems DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Largest BST in Binary Tree, Binary Tree, Binary Search Tree, Tree Traversal, Recursion, Time Complexity, Space Complexity, dynamic programming, tree properties, binary tree, binary search tree, recursion, tree traversal, BST Properties.
Largest BST in Binary Tree Given a binary tree, find the size of the largest subtree which is a Binary Search Tree (BST). A Binary Search Tree (BST) is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees. A single node tree is a BST. Input Specification The input will be the root of a binary tree. Each node will have an integer value. Output Specification Return an integer representing the number of nodes in the largest BST subtree. Constraints The number of nodes in the tree is between 0 and 10^4. Node values are between 10^5 and 10^5.