Take the 2-minute tour ×

I have a generic N-ary expression tree and I want to convert the same to a binary tree. Is there any well defined algorithms to do the same?

I tried going thro' different algorithms of converting N-ary tree to expression tree like https://groups.google.com/forum/?fromgroups#!topic/wncc_iitb/RrgohUZ-uhw but thats not going to work, as they don't worry about precedence and all.


share|improve this question
Can you expand on your requirements for the binary tree, vs the nary tree? Anything specific... or is your only requirement that children of a node, are simply still descendants of the same node? –  ChrisCM Jun 4 '13 at 13:52
add comment

1 Answer

Simple answer.

Step 1: Convert N-ary expression tree with different levels of precedence into an N-ary tree where each node has only a single level of precedence.

Step 2: Convert that tree into a binary tree.

If you're seeking a straightforward solution rather than an efficient one, it may be easy to explode each node into levels matching your precedence, then after you have a binary tree collapse out the obviously useless nodes. If you want a more efficient solution, then you'll want to be more cautious in the initial expansion.

share|improve this answer
add comment

Your Answer


