CareerCup

public class BinaryExpressionTree
{
   enum Operator
   {
      add(true), subtract(false), multiply(true), divide(false);

      private boolean symmetric;

      private Operator(boolean symmetric)
      {
         this.symmetric = symmetric;
      }

      boolean compare(OperatorNode a, OperatorNode b)
      {
         if (a.left.isEqual(b.left) && a.right.isEqual(b.right))
            return true;

         if (symmetric)
         {
            return (a.left.isEqual(b.right) && a.right.isEqual(b.left));
         }
         return false;
      }
   }

   abstract class Node
   {
      abstract boolean isEqual(Node other);
   }

   class OperatorNode extends Node
   {
      Operator operator;
      Node left;
      Node right;

      @Override
      boolean isEqual(Node other)
      {
         if (!(other instanceof OperatorNode))
         {
            return false;
         }

         OperatorNode n = (OperatorNode) other;
         if (operator != n.operator)
         {
            return false;
         }
         return operator.compare(this, n);
      }
   }

   class LeafNode extends Node
   {
      String value;

      @Override
      boolean isEqual(Node other)
      {
         if (!(other instanceof LeafNode))
         {
            return false;
         }

         LeafNode n = (LeafNode) other;
         return value.equals(n.value);
      }
   }

   boolean compare(Node a, Node b)
   {
      return a.isEqual(b);
   }
}

public class BinaryExpressionTree
{
   enum Operator
   {
      add(true), subtract(false), multiply(true), divide(false);

      private boolean symmetric;

      private Operator(boolean symmetric)
      {
         this.symmetric = symmetric;
      }

      boolean compare(OperatorNode a, OperatorNode b)
      {
         if (a.left.isEqual(b.left) && a.right.isEqual(b.right))
            return true;

         if (symmetric)
         {
            return (a.left.isEqual(b.right) && a.right.isEqual(b.left));
         }
         return false;
      }
   }

   abstract class Node
   {
      abstract boolean isEqual(Node other);
   }

   class OperatorNode extends Node
   {
      Operator operator;
      Node left;
      Node right;

      @Override
      boolean isEqual(Node other)
      {
         if (!(other instanceof OperatorNode))
         {
            return false;
         }

         OperatorNode n = (OperatorNode) other;
         if (operator != n.operator)
         {
            return false;
         }
         return operator.compare(this, n);
      }
   }

   class LeafNode extends Node
   {
      String value;

      @Override
      boolean isEqual(Node other)
      {
         if (!(other instanceof LeafNode))
         {
            return false;
         }

         LeafNode n = (LeafNode) other;
         return value.equals(n.value);
      }
   }

   boolean compare(Node a, Node b)
   {
      return a.isEqual(b);
   }
}

mathematically equivalent - the ones which evaluates to same value or the ones which are equal? a * b * (c / d) can be represented as

*
a		*
	b		/
		c		d

postfix - a b c d / * *
or
		*
	*			/
a		b	c		d

postfix -  a b * c d / *

Are these to be equivalent?

package google;

import google.ExpressionTreeEvaluation.ExpressionTreeNode.Operator;

public class ExpressionTreeEvaluation {
	public static class ExpressionTreeNode {
		static enum Operator {
			Add, Subtract, Multiply, Divide;

			public int performOperation(int operand1, int operand2) {
				switch (this) {
				case Add:
					return operand1 + operand2;
				case Subtract:
					return operand1 - operand2;
				case Multiply:
					return operand1 * operand2;
				default:
					return operand1 / operand2;
				}
			}

		}

		public Boolean isLeaf;
		public Operator valIfOperator;
		public Integer valIfInteger;

		ExpressionTreeNode left;
		ExpressionTreeNode right;

		public ExpressionTreeNode(boolean isLeaf, Operator valIfOperator, Integer valIfInteger) {
			this.isLeaf = isLeaf;
			if (isLeaf == true && valIfOperator == null && valIfInteger != null) {
				this.valIfInteger = valIfInteger;
			} else if (isLeaf == false && valIfOperator != null && valIfInteger == null) {
				this.valIfOperator = valIfOperator;
			} else {
				throw new IllegalArgumentException();
			}

			left = null;
			right = null;
		}

	}

	public static void main(String args[]) {
		ExpressionTreeNode n1 = new ExpressionTreeNode(false, Operator.Add, null);
		ExpressionTreeNode n2 = new ExpressionTreeNode(false, Operator.Divide, null);
		ExpressionTreeNode n3 = new ExpressionTreeNode(false, Operator.Add, null);
		ExpressionTreeNode n4 = new ExpressionTreeNode(true, null, 5);
		ExpressionTreeNode n5 = new ExpressionTreeNode(true, null, 5);
		ExpressionTreeNode n6 = new ExpressionTreeNode(true, null, 6);
		ExpressionTreeNode n7 = new ExpressionTreeNode(true, null, -1);

		n1.left = n2;
		n1.right = n3;
		n2.left = n4;
		n2.right = n5;
		n3.right = n7;
		n3.left = n6;

		
		ExpressionTreeNode en1 = new ExpressionTreeNode(false, Operator.Add, null);
		ExpressionTreeNode en2 = new ExpressionTreeNode(true, null, 3);
		ExpressionTreeNode en3 = new ExpressionTreeNode(true, null, 3);
		
		en1.left = en2;
		en1.right = en3;
		System.out.println(evaluateExpression(n1) == evaluateExpression(en1));
	}

	private static int evaluateExpression(ExpressionTreeNode node) {
		if (node.isLeaf) {
			return node.valIfInteger;
		} else {
			int left = evaluateExpression(node.left);
			int right = evaluateExpression(node.right);
			return node.valIfOperator.performOperation(left, right);
		}
	}
}

We have only a,b,* and + so there are no braces ("(",")"). Hence, we can convert a tree to string very simply and compare it with mathematical representation.

// This solution assumes in-order, though this question could be changed to pre-order or post-order.
// This solution also assumes that a node is a value when it is a leaf, and is an expression otherwise
// Code in C++

struct Node
{
  Node* left;
  Node* right;
  double val;
  std::string exp; // --, ++, +, -, *, /
}

bool checkTrees(Node* left, Node* right)
{
  if (left == NULL && right != NULL) return false;
  if (left != NULL && right == NULL) return false;

  return eval(left) == eval(right);
}

double eval(Node* node)
{
  if (node->left == node-> right == NULL)
    return node->val;

  if (node->left == NULL && node-> right != NULL)
    return compute(node->right, node->val);

  if (node->left != NULL && node-> right == NULL)
    return compute(node->left, node->val);  

  return compute(eval(node->left), node->exp, eval(node->right));
}

double compute(double valu, const std::string& exp)
{
  if (exp == "--") return val - 1.0;
  if (exp == "++") return val + 1.0;
  
  // ERROR - Invalid tree
  return 0.0;
}

double compute(double left, const std::string& exp, double right)
{
  if (exp == "+") return left + right;
  if (exp == "-") return left - right;
  if (exp == "*") return left * right;
  if (exp == "/") return left / right;

  // ERROR - Invalid tree
  return 0.0;
}

are we evaluating the expression inorder???

Read two expressions in order, then count a's, b's, and products of each and compare.

do depth-first traverse, at every operator level, sort left and right node with same comparator.
Then, simply see if 2 trees are identical.