Evaluation of binary expression tree
The coding challenge from top tech company onsite interview
Here I will describe the coding challenge from my onsite interview in one of the world’s famous top tech companies. Yes, the onsite interview was a pre-pandemic event. You traveled to company premises, everything was paid for. Flight, hotel, eating, and drinking for free! Unfortunately, nowadays onsite interviews are replaced with virtual interviews.
First, it was hard and time-consuming to get an invitation to an onsite interview. From first contact from a recruiter, sending CV back, then online coding challenge assessment, then two phone interviews with their engineer and recruiter. And yes, before they finally invite me, I should confirm that I would relocate myself to a foreign country in case of their offer.
On the onsite interview, I had 3 coding challenges and one system design interview. In the end, I didn’t receive an offer. But this coding challenge, which I describe, I performed well. Thus this was the easiest coding challenge, the other 2 were much more difficult.
The coding challenge was: Write a method that evaluates binary expression trees. A binary expression tree is a binary tree in which each internal node corresponds to the operator and each leaf node corresponds to the operand so for example expression tree for 3 + ((5+9) * 2) would be:
The result of the evaluation of this binary expression tree should be 31.
I had some 25–30 minutes to do this task. You code in the blank editor, no help from IDE (Integrated Development Environment), and no help from Google. The program should compile and work. Not easy?
When you receive a task like this, the worst thing you can do is to start coding without additional questions. You should ask if you understand the task well and about edge cases. If you don’t ask any questions, it means you don’t clarify things even in your everyday work. Nobody wants to employ a person who codes on his/her own, without clarification. It’s waste of time and money!
So I’ve asked a whole bunch of questions:
- What is the value of a binary tree? Is it a string data type that can contain either number or one of the operators +,-,*, and / ? Or binary tree node has 2 fields for values, one number field, and one operator field?
The answer was: The value of a binary tree is one string field.
2. If the value of a binary tree is a number (in string data format), is it some real number with decimal values (like 2.33), or is it some integer number (like 3)?
The answer was: It’s an integer number.
3. Can the tree be empty?
The answer was: No, it has at least one element.
4. Can I count that tree is in the correct state? In the other words, is it a well-formed binary expression tree?
The answer was: Yes, it’s a well-formed binary expression tree.
5. Is division by zero possible?
The answer was: No, it isn’t possible.
When I received all these answers, I started coding. During coding, I explained what I did. In short, I said there were 2 main ways of tree (or graph) traversals: BFS (Breadth-First Search) and DFS (Depth-First Search). Among DFS there were 3 main ways of tree traversal: in-order traversal (left-node-right), post-order traversal (left-right-node) and pre-order traversal (node-left-right). BFS was usually used in graph path problems. So naturally, we would use DFS here, DFS pre-order traversal. It was the most natural to use pre-order traversal because we needed to see what was the node value to decide what to do next: if it was a number, then it was the leaf and we should return that number immediately; if it was operator then we needed to see the overall value of left tree (as number) and overall value of right tree (as number too) to apply the operator over these values.
Final solution was:
The final words were about the runtime and space complexity of the solution. Runtime complexity was O(N) because we traverse each node only once (N is the number of tree nodes).
What about space complexity? For DFS tree traversal, which goes along a single ‘tree branch’ all the way down and uses a stack implementation (each recursive method call is put on the stack), the height of the tree matters. The space complexity for DFS is O(h) where h is the maximum height of the tree. In general, the tree can be skewed (like a list, all nodes on one branch) and in that case, space complexity is also O(N).
Regarding skewed binary expression tree, because leaves are numbers and nodes are binary operators, each level (except root level) of skewed binary expression tree contains 2 nodes, so space complexity is O(N/2). However, because Big-O notation doesn’t care about constants, final space complexity is also O(N).
Conclusion
Here was described the successful response to the coding challenge. The better you know how it looks like in reality — the better are chances you will succeed in your attempts to be a part of the top-tech community.
Good luck and keep coding!
