Katkat
Back

Solve Expression and Tree-List Problems

PinterestMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests recursive backtracking for expression generation and pointer manipulation for in-place tree-to-linked-list conversion.

Part 1: Expression Generation

Given a string num containing only digits and a target integer target, return all possible strings you can form by inserting binary operators '+', '-', or '*' between the digits such that the resulting expression evaluates to target under a strict left-to-right evaluation rule (ignoring standard operator precedence).

Example: Input: num = "123", target = 6 Output: ["1+2+3", "1*2*3"]

Part 2: Tree to Doubly Linked List

Convert a Binary Search Tree (BST) into a sorted circular doubly-linked list in-place. You are modifying the tree nodes such that the left pointer points to the predecessor and the right pointer points to the successor. The smallest node should point to the largest, and vice-versa.

Interface:

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Constraints

  • For Part 1: 1 <= num.length <= 10, num consists of digits 0-9.
  • For Part 2: Number of nodes is N (1 to 10^4).

Hints

Hint 1

For Part 1, use backtracking to explore every possible operator insertion between digits, maintaining the current running total.

Hint 2

For Part 2, perform an in-order traversal of the BST and maintain a pointer to the 'previous' node processed to stitch the list together.

Hint 3

Remember to handle the circular connection by linking the head and tail nodes after the traversal completes.

Follow-up questions

  • How would you modify the Part 1 solution to support standard operator precedence (PEMDAS)?
  • What is the space complexity of your Part 2 solution if you cannot use an explicit stack (e.g., Morris Traversal)?
  • How would you optimize the expression generator if you were allowed to use parentheses?