How many binary trees possible with N nodes using Catalan Number concept

Question

So I was understanding Catalan Number Concept and try to implement it in code using topDown DP approach, so the recurrence relation is from what I have learned,

f(N) signifies total count of binary search trees possible by N number of nodes

f(N) = f(i-1).f(N-i)

where, 
i = 1.....N (i signifies root node and traverse through all the nodes),
N is total number of nodes present in the binary tree,
f(i-1) signifies number of left subtrees possible when i is a root node,
f(N-i) signifies number of right subtrees possible when i is a root node.

there's a mathematical formulae by which we can find f(N) value,

2NcN/(N+1)

. And, total count of binary trees possible by N number of nodes,

(factorial of N) * f(N)

My Doubt:

what's the difference between binary trees and binary search trees? I feel like both are defines same meaning but there's a difference that I'm not aware of so help me.

Answer 1

What's the difference between binary trees and binary search trees?

There is no difference in the shape of such trees, but binary search trees put a constraint on the values that its nodes have, which doesn't exist for (just) binary trees:

• The value of a node must not be less than any of the values in its left subtree
• The value of a node must not be greater than any of the values in its right subtree

Another way to express this constraint is:

• The in-order traversal of the values in the tree must be non-decreasing.

Practically this means that when you have been given:

• A shape of a binary tree with nodes
• A set of unique values that are present in the tree

...then there is only one possibly way to associate those values with the tree's nodes for it to be a binary search tree. If it does not have to be a binary search tree, then there are ! ways to make that association.

Conclusions:

Given , then (the ^th Catalan number) represents:

• the number of binary trees with nodes without values (i.e. number of shapes of binary trees)
• the number of binary search trees with distinct values

The number of binary trees with distinct values is !