Ambiguity lies in the heart of this question.
If you are given a tree and you want to look for leaf nodes you can
simply do an inorder traversa,
and check for leaf nodes.
Time complexity will be O(N) and space complexity will be O(log N).
void
getLeafNodes (node *root) {
if (! root) return;
getLeafNodes (root->left);
if (! root->left && ! root->right) printf ("%d ", root->data);
getLeafNodes (root->right);
return;
}
However, as @Saurabh told - if you are simply given an array of values
which would result from inorder traversal,
and not the tree itself, you can *not* create a unique tree. It follows
that you can not identify leaf nodes.
In fact with a given number of nodes (say N), there are (1 / (n + 1))
*2nCn (catalan number) possibility to form a tree which annihilates any
possibility even remote to search for the uniqueness.
Perhaps OP could be lucid.
On 3/16/13 9:48 PM, Saurabh Paliwal wrote:
I don't think so. If I understand your problem well, I have a
counter-example
take for example - >
Inorder Traversal - 1-2-3
this could mean a binary tree rooted at 2 with 2 leaf nodes 1 and 3
but this could also mean a binary tree rooted at 3 with 2 as its left
child which in-turn has 1 as its left child (the only leaf node).
On Sat, Mar 16, 2013 at 7:44 PM, Megha Agrawal <megha1...@iiitd.ac.in
<mailto:megha1...@iiitd.ac.in>> wrote:
Hello all,
Is it possible to get leaf nodes from inorder traversal of a
binary tree(not BST)?
--
Thank you
--
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it,
send an email to algogeeks+unsubscr...@googlegroups.com
<mailto:algogeeks%2bunsubscr...@googlegroups.com>.
For more options, visit https://groups.google.com/groups/opt_out.
--
- Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups "Algorithm
Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
