Evaluating an arithmetic expression from a binary tree

Question

Let's say I have a Binary Tree that looks like

 +
 2 *
 5 8 

I've written a function to traverse inorder to solve it as 2+5*8

Is there a better way? Using eval seems a bit hacky and perhaps I can just have a function calculate the total sum on either side and then do a left + right instead.

class Node {
 constructor(value) {
 this.value = value;
 this.left = null;
 this.right = null;
 }
}
class BinarySearchTree {
 constructor() {
 this.root = null;
 }
 
 solveEquation() {
 let equation = "";
 let traverse = (currentNode = this.root) => { 
 if (currentNode !== null) {
 if (currentNode.left !== null) traverse(currentNode.left);
 equation += currentNode.value;
 if (currentNode.right !== null) traverse(currentNode.right);
 }
 }
 
 traverse();
 return eval(equation);
 }
 init() {
 this.root = new Node('+');
 let currentNode = this.root;
 currentNode.left = new Node(2);
 currentNode.right = new Node('*');
 currentNode = currentNode.right;
 currentNode.left = new Node(5);
 currentNode.right = new Node(8);
 }
}
let bst = new BinarySearchTree();
bst.init();
console.log(bst.solveEquation());

• 200_success: The input is a binary tree, but in what sense is it a binary search tree?

Answer 1

This is not a search tree. You can call it an abstract syntax tree, or just a binary tree.

You can use a dispatch table to evaluate ops.

 dispatch = {
 '+': (a,b) => a+b,
 '*': (a,b) => a*b
 }
 ...
 if (node.left && node.right && node.value in dispatch) dispatch[node.value]( traverse(node.left), traverse(node.right) );