What are the total number of possible ordered trees with N nodes?

algorithm tree structure computer-science catalan
abhilash_goyal picture abhilash_goyal · Aug 9, 2013 · Viewed 8.1k times · Source

For example for N=3, we can find easily by listing them all, but when asked for any arbitrary N value I am facing problem.

Answer

user1650846 picture user1650846 · Aug 11, 2013

If you are looking at binary trees then, as mcdowella said, Choose(2n,n)/(n+1) (Catalan number) is the answer.

If you are looking at arbitrary trees then it is probably n. n^(n-2) = n^(n-1), but I am not totally sure. Prufer's algo tells us that there are n^(n-2) labeled trees and any of the nodes can be made a root, thus we get the number n^(n-1).

Related questions

What is the difference between tree depth and height?

This is a simple question from algorithms theory. The difference between them is that in one case you count number of nodes and in other number of edges on the shortest path between root and concrete node. Which is which?

Read More
What is the most efficient/elegant way to parse a flat table into a tree?

Assume you have a flat table that stores an ordered tree hierarchy: Id Name ParentId Order 1 'Node 1' 0 10 2 'Node 1.1' 1 10 3 'Node 2' 0 20 4 'Node 1.1.1' 2 10 5 'Node 2.1' 3 10 6 'Node 1.2' 1 20 Here's a diagram, where we have [id] Name. Root node 0 is fictional. [0] …

Read More
Non-recursive depth first search algorithm

I am looking for a non-recursive depth first search algorithm for a non-binary tree. Any help is very much appreciated.

Read More