We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Build Binary Expression Tree From Infix Expression

Number: 1736

Difficulty: Hard

Paid? Yes

Companies: Amazon

Problem Description

Given an infix arithmetic expression containing single-digit operands, the operators '+' , '-' , '*' , '/' and parenthesis, construct any binary expression tree whose in-order traversal (ignoring parentheses) produces the original expression. The tree must respect the operator precedence (multiplication and division before addition and subtraction) and the evaluation rule that expressions within parentheses are computed first.

Key Insights

  • Use a modified version of the Shunting Yard algorithm to respect operator precedence and associativity.
  • Maintain two stacks: one for tree nodes (operands) and one for operators.
  • When encountering an operator, build subtrees by popping from the operator stack if the current operator has lower or equal precedence than the operator at the top.
  • Parentheses are used to temporarily override the natural precedence and must be handled separately.
  • Finally, after processing the entire string, combine any remaining nodes in the stacks to build the complete tree.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the expression, since we process each character once. Space Complexity: O(n) due to the stacks used to store nodes and operators.

Solution

We use two stacks to construct the expression tree:

  1. Operand Stack: Stores tree nodes (each with left and right child pointers).
  2. Operator Stack: Stores operators (and a special marker for '(').

As we scan the expression:

  • If the current character is a digit, we create a new node and push it on the operand stack.
  • If the character is an opening parenthesis '(', push it onto the operator stack.
  • If it is a closing parenthesis ')', pop operators from the operator stack and combine nodes from the operand stack into subtrees until an opening parenthesis is encountered.
  • For an operator, while the operator stack is not empty (and its top has higher or equal precedence compared to the current operator), pop the operator and create a subtree by popping two nodes from the operand stack (left operand and right operand). Push the formed subtree back into the operand stack. Then push the current operator onto the operator stack.

After processing the entire expression, merge any remaining operators with their respective operands from the stack to get the final binary expression tree.

Code Solutions

# Define the TreeNode class for the binary expression tree.
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# Function to define precedence of operators.
def precedence(op):
    if op in "*/":
        return 2
    if op in "+-":
        return 1
    return 0

def buildExpressionTree(s: str) -> TreeNode:
    operands = []  # Stack for tree nodes.
    operators = [] # Stack for operators.

    def buildSubtree():
        # Pop an operator and two operands to form a subtree.
        op = operators.pop()
        right = operands.pop()
        left = operands.pop()
        node = TreeNode(op)
        node.left = left
        node.right = right
        operands.append(node)

    i = 0  # Index pointer for the expression.
    while i < len(s):
        ch = s[i]
        if ch.isdigit():
            # Create a node for the operand and push onto the operands stack.
            operands.append(TreeNode(ch))
        elif ch == '(':
            operators.append(ch)
        elif ch == ')':
            # Process until the corresponding '(' is found.
            while operators and operators[-1] != '(':
                buildSubtree()
            operators.pop()  # Remove the '(' from the stack.
        elif ch in "+-*/":
            # While top of operator stack has greater or equal precedence, build subtree.
            while (operators and operators[-1] != '(' and
                   precedence(operators[-1]) >= precedence(ch)):
                buildSubtree()
            operators.append(ch)
        # Move to the next character.
        i += 1

    # Build any remaining subtrees.
    while operators:
        buildSubtree()

    return operands[-1]

# Example usage:
# s = "3*4-2*5"
# tree = buildExpressionTree(s)
# The constructed tree's in-order traversal should reproduce "3*4-2*5" (without parentheses).
← Back to All Questions