Count number of binary search tree created for array of size n

Nov 9, 2018 21:47 · 98 words · 1 minute read

This problem is an example of “catalan Numbers problem”

The Question is as follows Count number of binary search tree created for array of size n

Solution in golang

package main

import (
	"fmt"
)

func main() {

	for i := 0; i < 20; i++ {
		fmt.Println(i, countTreesRec(i))
	}

}

func countTreesRec(numKeys int) int {
	if numKeys <= 1 {
		return 1
	} else {
		sum := 0

		for root := 1; root <= numKeys; root++ {
			left := countTreesRec(root - 1)
			right := countTreesRec(numKeys - root)
			sum += left * right
		}
		return sum
	}
}