Create Expression Tree

Expression tree is a binary tree in which each internal node corresponds to operator and each leaf node corresponds to operand.

Solution:

• Fist convert infix to postfix
• Iterate postfix expression with stack

Algorithm

1. Create stack
2. Iterate expression string from start to end
3. If currentCharacter is operand then
   1. Create Binary Tree Node with this operand
   2. stack.push(node)
4. Else
   1. operand1 = stack.pop
   2. operand2 = stack.pop
   3. create node with currentCharacter
   4. node.left = operand2
   5. node.right = operand1
   6. stack.push(node)
5. return stack.pop

Latest Source Code:
Github: ExpressionTreeCreator.java

Output:

Infix: A + B * C + D
Expression Tree 
       +               
      / \       
     /   \      
    /     \     
   /       \    
   +       D       
  / \           
 /   \          
 A   *           
    / \         
    B C         
                                

Infix: (A + B) * (C + D)
Expression Tree 
   *       
  / \   
 /   \  
 +   +   
/ \ / \ 
A B C D 
                

Infix: A * B + C * D
Expression Tree 
   +       
  / \   
 /   \  
 *   *   
/ \ / \ 
A B C D 
                

Infix: A + B + C + D
Expression Tree 
       +               
      / \       
     /   \      
    /     \     
   /       \    
   +       D       
  / \           
 /   \          
 +   C           
/ \             
A B