[News]

News: Welcome to The Oktave Forum.

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

Here is another puzzle to act as your mind's screen saver (i.e. keep it busy when it is idle.. )

You are given a sequence of n symbols and are told that this sequence was generated by the in-order traversal of a binary tree. How many binary trees can you generate from this sequence, whose in-order traversal gives you back the sequence?

As always, I don't have a closed-form solution for it yet (and am not too keen on searching for a solution over the web). So, I'll applaud promising directions giving even first-order solutions like a recurrence relation, etc.

[bn vikram]

bn vikram

bn vikram

Show bn vikram's last posts.

Show general stats for bn vikram.

• 
• Newbie
• Karma: 2
• Posts: 2

Case n=1 ----- only 1 way
Case n=2 ------ there are 2 ways
Case n=3 -----
-   Convert the sequence to post order form
-   Consider for ex the sequence (abc)
-   In post order it is (acb)
-   The first element in the original sequence should be either the 1st element of the post order sequence or the last element.
-   i.e. a(cb) or (cb)a
-   the other two elements form the case n=2
-   totally 2*case n=2  i.e. 4 ways
in general ---- we can start from the last element in the sequence and start adding elements to it. In each case the element can be added either at the front of the post order or in the last. Hence doubling the no. of previous cases .
hence the general formula would be
p(n)=2*p(n-1)

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

*applause* (your karma has increased..)

One way to look at this is, suppose we have some tree (let us call it t(n-1)) generated out of n-1 elements and we have to extend this sequence by one element (let us call it x). This can be done by either making t(n-1) as a left sub tree that is rooted at x, or x as the right child of the right-most leaf of t(n-1). In both these cases, t(n-1) will be enumerated first before x.

[Nirav]

Nirav

Nirav

Show Nirav's last posts.

Show general stats for Nirav.

• 
• Newbie
• Karma: 2
• Posts: 6

In fact, there are 5 possible trees with length of inordered traversal sequence as 3.

If the inordered traversal sequence is ABC then possible trees would be,

    B
   A C

    A
     B
      C

    A
     C
    B

    C
   B
  A
   
    C
   A
    B

Given only inorder traversal, every node can be possibly a root node and the nodes to left of that node and right of that node would be its left and right subtrees respectively, which number of trees could be found out in a recursive manner.

With only one node in the inordered sequence, there could be only one tree possible. so, p(1) = 1.

With no nodes in either left or right sub tree, it's again one tree only, i.e. without any node. so p(0) = 1. (This is debatable)

So, while considering first node in the sequence as root node, we say there is no left sub tree and rest n-1 nodes form right subtree.
with second node as root node, there is 1 node in left subtree and n-2 nodes in right subtree.
with third node as root node, there are 2 nodes in left subtree and n-3 nodes in right subtree... and so on.

So, No. of possible trees = sum of (left subtrees possible * right subtrees possible) with each node considered as root node one by one.
p(n) = Sum over x=0 to n-1 (p(x) * p((n-(x+1)))

p(0) = 1
p(1) = 1
p(2) = p(0)*p(1) + p(1)*p(0) = 1*1 + 1*1 = 2
p(3) = p(0)*p(2) + p(1)*p(1) + p(2)*p(0) = 1*2 + 1*1 + 2*1 = 5

@ Vikram,
If the first element of the original sequence is root node of left subtree with that root without any left subtree, then first element would not go either at first or last of the post order traversal.

@ Prof. Srinath
If an element is added in the tree i.e. p(n+1), it is possible that that element could be added in the between the sequence also rather than only at ends of the sequence.

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

I think you have a point; let me look at your answer more closely when I get some time.