Katkat
Back

Solve Tree Views, Columns, and Calculator

MetaMachine Learning Engineer · Onsite
EasyMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to perform recursive binary tree traversals to extract horizontal and vertical views, followed by implementing a stack-based parser to handle mathematical expressions with standard order of operations.

Part 1: Vertical Tree View

Given the root of a binary tree, return the vertical order traversal of its nodes' values. Nodes are ordered from top to bottom, left to right. If two nodes are in the same column and row, order them left-to-right.

Function Signature

def vertical_order(root: Optional[TreeNode]) -> List[List[int]]:

Example

Input: [3,9,20,null,null,15,7] Output: [[9],[3,15],[20],[7]] Explanation: Column -1: [9] Column 0: [3, 15] Column 1: [20] Column 2: [7]

Part 2: Arithmetic Calculator

Given a string s representing a non-negative integer expression, implement a calculator that evaluates the string. The expression contains only non-negative integers, '+', '-', '*', and '/' operators. Integer division should truncate toward zero.

Function Signature

def calculate(s: str) -> int:

Constraints

  • 1 <= s.length <= 3 * 10^5
  • s consists of integers, operators, and spaces.
  • All intermediate results fit in a 32-bit signed integer.

Example

Input: s = "3+2*2" Output: 7

Edge Cases

  • Empty strings or strings with only whitespace.
  • Expressions with no operators (single integers).
  • Sequences of high-precedence operators (e.g., 10/2*3).

Hints

Hint 1

For the vertical view, use a dictionary to map column indices to node values, keeping track of depth to ensure top-down ordering.

Hint 2

For the calculator, use a stack to store results of addition/subtraction, while immediately processing multiplication and division against the last seen number.

Hint 3

When traversing the tree, consider a Breadth-First Search (BFS) approach with a queue storing (node, column, depth) to naturally handle the level-by-level requirement.

Follow-up questions

  • How would you modify the calculator to support parentheses like '(1+(4+5+2)-3)+(6+8)'?
  • In the tree problem, if the tree is extremely deep and skewed, how does the memory complexity of your approach change?
  • How would you handle floating-point precision if the division requirement changed from truncation to standard decimal division?