Build Binary Expression Tree From Infix Expression

This page explains Java solution to problem Build Binary Expression Tree From Infix Expression using Tree data structure.

Problem Statement

A binary expression tree is a kind of binary tree used to represent arithmetic expressions. Each node of a binary expression tree has either zero or two children. Leaf nodes (nodes with 0 children) correspond to operands (numbers), and internal nodes (nodes with 2 children) correspond to the operators + (addition), - (subtraction), * (multiplication), and / (division).

For each internal node with operator o, the infix expression that it represents is (A o B), where A is the expression the left subtree represents and B is the expression the right subtree represents.

You are given a string s, an infix expression containing operands, the operators described above, and parentheses ( and ).

Return any valid binary expression tree, which its in-order traversal reproduces s after omitting the parenthesis from it (see examples below).

Please note that order of operations applies in s. That is, expressions in parentheses are evaluated first, and multiplication and division happen before addition and subtraction.

Operands must also appear in the same order in both s and the in-order traversal of the tree.

Input: "2-3/(5*2)+1"
Output: [+,-,1,2,/,null,null,null,null,3,*,null,null,5,2]

Input: "3*4-2*5"
Output: [-,*,*,3,4,2,5]

Input: "1+2+3+4+5"
Output: [+,+,5,+,4,null,null,+,3,null,null,1,2]

Solution

package com.vc.hard;

import java.util.*;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
class BuildBinaryExpressionTreeFromInfixExpression {
    public TreeNode expTree(String s) {
        Queue<Character> q = new LinkedList<>();
        for(int i = 0; i < s.length(); i++) {
            q.offer(s.charAt(i));
        }
        return helper(q);
    }

    private TreeNode helper(Queue<Character> q) {
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();

        char prevSign = ' ';
        while(!q.isEmpty()) {
            char ch = q.poll();

            if(Character.isDigit(ch) || ch == '(') {
                TreeNode currentOperand = ch == '(' ? helper(q) : new TreeNode(ch);

                if(prevSign == '-' || prevSign == '+') {
                    deque.addLast(new TreeNode(prevSign));
                    deque.addLast(currentOperand);
                }
                else if(prevSign == '*' || prevSign == '/') {
                    TreeNode prevOperand = deque.pollLast();
                    TreeNode signNode = new TreeNode(prevSign);
                    signNode.left = prevOperand;
                    signNode.right = currentOperand;
                    deque.addLast(signNode);
                }
                else {
                    deque.addLast(currentOperand);
                }
            }
            else if(ch == ')') break;
            else prevSign = ch;
        }

        while(deque.size() > 1) {
            TreeNode first = deque.pollFirst();
            TreeNode operator = deque.pollFirst();
            TreeNode second = deque.pollFirst();

            operator.left = first;
            operator.right = second;
            deque.addFirst(operator);
        }
        return deque.pollLast();
    }
}

Time Complexity

O(N) Where
N is number of characters in an input String s

Space Complexity

O(N) Where
N is number of characters in an input String s