Google | Onsite | Compare Expression Trees
4905
Jul 19, 2019
Aug 01, 2019

Given 2 binary expression trees tree1 and tree2. The leaves of a binary expression tree are variable names and the other nodes contain operators. Find out if the expressions represented by these trees are equal or not.
There are only plus signs + and letters in the tree. Input is guaranteed to be valid.

Example 1:

Input:
	 tree1
	   +
	 /   \
	a     b

	 tree2
	   +
	 /   \
	b     a
Output: true
Explanation: a + b = b + a

Example 2:

Input:
	 tree1
		+
	  /   \
	 a     +
		  / \
		 c   de

	 tree2
		+
	  /   \
	 +     de
	/ \
   a   c

Output: true
Explanation: a + (c + de) == (a + c) + de

Example 3:

Input:
	 tree1
	   +
	 /   \
	a     b

	 tree2
	   +
	 /   \
	c     d
Output: false
Explanation: a + b != c + d

Follow-up:
Minus - sign is allowed. For example

    +
  /   \
 a     -
      / \
     c   d

a + (c - d)
Comments (15)