Infix expression to a binary expression tree

July 14, 2018

Introduction

It is the second meeting with a peer after six months. We met together this January 2018. And then I gave him the algorithm to work on which is to construct binary expression tree using infix expression.

Problem solving

The peer is very strong at coding skills, so he chose the optimal solution linear time O(N), and tried very hard to figure out how to design parsing algorithm using stack.

Here is the transcript how he approached the problem. I can tell that he is very smart on time complexity compared to me.

My feedback

The peer did very good to find optimal solution, try to use stack to parse the string once and build a binary expression tree. The time complexity is O(N), N is length of infix expression. And the peer communicated very well, there are multiple solutions and he decided to push the number and operator to the stack and also build a binary tree node in the same time. Somehow he should think about validation of expression string, and also try to simplify the code. 

Here is my feedback gist.

Statistics

Meeting time July 14, 2018 9:00 AM PST - 11:10 AM PST

First the peer worked on the infix expression to binary expression tree, and then I worked on the two algorithms, discussion of "Find a path with minimum maximum value in the matrix".

Follow up 

July 16, 2018


I wrote C# code to implement the algorithm using O(N) time complexity, N is the expression length.