Subramanya's Digital Garden

Recent Notes

95. Unique Binary Search Trees II

2 min read

links: Algorithms MOC

Unique Binary Search Trees - 2

Problem:

Given an integer n, return all the structurally unique **BST’**s (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

Solution:

These are the concepts that needs to be looked into:

  1. Go through each index and generate left and right binary search trees in a format for left it will be start to i - 1 and for right i + 1 to end
  2. For each left sub tree and right sub tree create a node with i and attach each left and right

Top Down Approach

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function(n) {
  return treeGenerator(1, n)
};
 
function treeGenerator(start, end) {
  const result = []
 
  if(start > end) {
    result.push(null)
    return result
  }
 
  if(start === end) {
    result.push(new TreeNode(start))
    return result
  }
 
  for (let i = start; i <= end; i++) {
    const leftSubTrees = treeGenerator(start, i - 1)
    const rightSubTrees = treeGenerator(i + 1, end)
 
    for (const leftSubTree of leftSubTrees) {
      for (const rightSubTree of rightSubTrees) {
        const root = new TreeNode(i)
        root.left = leftSubTree
        root.right = rightSubTree
        result.push(root)
      }
    }
  }
 
  return result
}

tags: dynamic-programming backtracking binarysearchtree

sources:

Graph View