1

This Wolfram link talked a bit about 'Labelled' Binary tree. So is there something called 'Unlabelled' binary tree as well ? A concise explanation of Both would be really nice.

Why am i searching for this ?
I'm trying to answer this question :

We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

Now, i know the number of Binary trees given n nodes is the nth Catalan number, but now i'm confused : which of the above two types does this formula apply to then ?

PS: some help with the question in quotes would be very nice too :)

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
Somjit
  • 2,503
  • 5
  • 33
  • 60
  • According to [this SO article](http://stackoverflow.com/questions/14900693/enumerate-all-full-labeled-binary-tree), a labeled binary tree is one where all leaf nodes have a label. But since your problem states that all nodes are unique, I don't see the point of even mentioning unlabeled. – Tim Biegeleisen Apr 16 '15 at 08:12
  • To talk about the solution to the initial problem I would like to see any restriction on input - for example, how large `N` can be? – ivan.mylyanyk Apr 16 '15 at 08:15
  • The SO link kinda goes against the Wolfram Link. And my guess was that a Binary search tree is unique given a set of unique entries. Is there a difference between a Binary tree and a Binary Search tree in this uniqueness context ? Also, when does that catalan number apply ? – Somjit Apr 16 '15 at 08:22
  • Binary tree - just a simple tree where every node has up to two children. Binary **search** tree is a binary tree (condition above applies), where we have additional condition - the key in any node is larger than the keys in all nodes in that node's left sub-tree and smaller than the keys in all nodes in that node's right sub-tree. – ivan.mylyanyk Apr 16 '15 at 08:31

2 Answers2

2

A binary tree can have labels assigned to each node or not. For a given unlabeled binary tree with n nodes we have n! ways to assign labels. (Consider an in-order traversal of the nodes and which we want to map to a permutation of labels 1..n)

From the above we can see that nth Catalan number gives the number of unlabeled binary trees.

Take for example n = 3. We have the following trees 5 trees:

1. o      2. o       3.  o      4.  o   5. o 
    \         \         / \        /      / 
     o         o       o   o      o      o  
    /           \                /        \
   o             o              o          o

in general this number is given by the formulae of the N-th Catalan Number.

To get the number of labeled trees you have to multiply by n! so for n = 3 we have 30 trees in total. Basically for each of the five unlabeled BSTs above we create !3 = 6 labeled BSTs with labels:

1: 1, 2, 3
2: 1, 3, 2
3: 2, 1, 3
4: 2, 3, 1
5: 3, 1, 2
6: 3, 2, 1

Hope this helps to understand the difference.

Andrei Antonescu
  • 73
  • 1
  • 6
0

Well, as far as I understood, the "unlabeled" means that we don't know the nodes of this tree. The problem then asks us how many different ways to assign the element to the node so the tree will be binary search tree.

UPDATE: It means that we want to set value for each node from that N elements, so we don't break the main binary search tree condition. It means that after all nodes have values, we still have binary tree - that the key in any node is larger than the keys in all nodes in that node's left sub-tree and smaller than the keys in all nodes in that node's right sub-tree.

Binary search tree on Wikipedia

ivan.mylyanyk
  • 2,051
  • 4
  • 30
  • 37
  • if all nodes are unique, there can be only one BST right ? – Somjit Apr 16 '15 at 08:23
  • @Somjit no. For example, if you have nodes 1,2,3 you can have a few binary search trees: `(1)` at the root and `(2)` - right child of `1`, `(3)` - right child of `2`. ***Another version***: `(2)` - the root, `(1)` - left child of `(2)` and `(3)` - right child of `(2)`. – ivan.mylyanyk Apr 16 '15 at 08:28