Evaluate Expression Tree

# Evaluate Expression Tree ## Difficulty Medium ## Tags `tree`, `recursion` ## Problem Statement Given a binary expression tree, evaluate it and return the result. In this tree: - **Leaf nodes** contain integer values. - **Internal nodes** contain operators: `+`, `-`, `*`, `/`. The division operator `/` represents integer division (truncate toward zero). ## Constraints - The tree is a valid binary expression tree. - All leaf nodes contain integers. - All internal nodes have exactly two children. - No division by zero. ## Signatures ### Python ```python def evaluate_tree(root: TreeNode) -> int: pass ``` ### Java ```java public class Solution { public int evaluate_tree(TreeNode root) { return null; } } ``` ### Csharp ```csharp public class Solution { public int evaluate_tree(TreeNode root) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: int evaluate_tree(TreeNode* root) { } }; ``` ### C ```c int evaluate_tree(TreeNode* root) { } ``` ### Ruby ```ruby def evaluate_tree(root) end ``` ### Perl ```perl sub evaluate_tree { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def evaluate_tree(root: TreeNode): Int = { } } ``` ### Haskell ```haskell evaluate_tree :: ... -> ... evaluate_tree args = undefined ``` ### Clojure ```clojure (defn evaluate_tree [root] ) ``` ### Scheme ```scheme (define (evaluate_tree root) ) ``` ## Examples ### Example 1 **Input:** ``` + / \ 3 * / \ 5 2 ``` **Output:** ``` 13 ``` **Explanation:** 3 + (5 * 2) = 3 + 10 = 13 ### Example 2 **Input:** ``` - / \ * + / \ / \ 4 5 2 3 ``` **Output:** ``` 15 ``` **Explanation:** (4 * 5) - (2 + 3) = 20 - 5 = 15 ### Example 3 **Input:** ``` / / \ 10 3 ``` **Output:** ``` 3 ``` **Explanation:** 10 / 3 = 3 (integer division) ## Hints 1. Use recursive post-order traversal. 2. If node is a leaf (no children), return its integer value. 3. Otherwise, evaluate left subtree, evaluate right subtree, apply operator. 4. For Python integer division truncating toward zero, use `int(a / b)` not `a // b`.