Requirements to Construct a Unique Binary Tree
Hard Problems DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Requirements needed to construct a Unique Binary Tree, Binary Tree, Dynamic Programming, Tree Construction, Recursion, Time Complexity, Space Complexity, Combinatorics, inorder traversal, binary tree, tree construction, preorder traversal, data structures, postorder traversal, tree traversal, Construct Tree from Traversals.
Number of Unique Binary Search Trees Problem Statement Given an integer n, return the number of structurally unique Binary Search Trees (BSTs) that can be constructed using n nodes, each node storing a unique value from 1 to n. A Binary Search Tree (BST) is a rooted binary tree data structure with the following properties: The value of each node is greater than or equal to any value in its left subtree. The value of each node is less than or equal to any value in its right subtree. Both the left and right subtrees must also be BSTs. Input The input consists of a single integer n (1 <= n <= 19). Output Return the count of structurally unique BSTs. Examples Example 1: Input: n = 3 Output: 5 Explanation: For n = 3, there are a total of 5 unique BSTs: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 Example 2: Input: n = 1 Output: 1 Constraints 1 <= n <= 19