1

I am trying to solve the following algorithm question:

You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.

The null node needs to be represented by empty parenthesis pair "()". And you need to omit all the empty parenthesis pairs that don't affect the one-to-one mapping relationship between the string and the original binary tree.

Example 1: Input: Binary tree: [1,2,3,4]

       1
     /   \
    2     3
   /
  4

Output: "1(2(4))(3)"

Explanation: Originallay it needs to be "1(2(4)())(3()())", but you need to omit all the unnecessary empty parenthesis pairs. And it will be "1(2(4))(3)".

Example 2: Input: Binary tree: [1,2,3,null,4]

       1
     /   \
    2     3
     \
      4

Output: "1(2()(4))(3)"

Explanation: Almost the same as the first example, except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.

I have written the following code:

class TreeNode {
    constructor(val, left, right) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
    }
}

const tree2str = (t) => {
    const result = []
    const stack = []

    const dfs = (current) => {
        if (current === null) return
        result.push(current.val)
        if (!current.left && current.right) result.push('(')
        if (current.left) {
            result.push('(')
            stack.push(')')
            dfs(current.left)
        }
        while (stack.length) {
            result.push(stack.pop())
        }
        if (!current.left && current.right) stack.push(')')
        if (current.right) {
            result.push('(')
            stack.push(')')
            dfs(current.right)
        }
    }
    dfs(t)
    return result.join('')
}

The test cases I have so far:

const tree = new TreeNode(1, new TreeNode(2, new TreeNode(4)), new TreeNode(3))
const tree2 = new TreeNode(1, new TreeNode(2, null, new TreeNode(4)), new TreeNode(3))
const tree3 = new TreeNode(1, new TreeNode(2, new TreeNode(3), new TreeNode(4)))

console.log(tree2str(tree)) // "1(2(4)())(3()())" ==> "1(2(4))(3)"
console.log(tree2str(tree2)) // "1(2()(4))(3)"
console.log(tree2str(tree3)) // "1(2(3)(4))" instead got "1(2(3))(4)"

Only two work, however, I am having trouble with the third, and can't spot where I am going wrong.

Improve this question
1
  • Why do you have to empty the whole stack with while (stack.length) ? That said, why do you need stack at all? return val + "(" + recurse(left) + ")(" + recurse(right + ")"; Commented May 11, 2020 at 21:48

2 Answers 2

Reset to default
1

The stack makes things a bit more complicated. The bug was that eventually you would pop the stack twice in your last test case and that would mess up the open-close parenthesis. I removed the stack and made the code a bit easier to debug. However, I have used the dual-stack approach for interpreting arithmetic expression, but that seems unnecessary here.

You can try the code out at this sandbox: https://codesandbox.io/s/need-help-constructing-string-with-parenthesis-from-binary-tree-p3sk3?file=/src/index.js

const tree2str = t => {
  const result = [];
  const dfs = current => {
    if (!current) {
      return;
    }

    const { val, left, right } = current;
    if (val !== null && val !== undefined) {
      result.push(val);
      if (left) {
        result.push("(");
        dfs(left);
        result.push(")");
      } else if (!left && right) {
        result.push("()");
      }

      if (right) {
        result.push("(");
        dfs(right);
        result.push(")");
      }
    }
  };
  dfs(t);
  return result.join("");
};

This version seems to produce the results you were looking for. That was fun though!

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

I added this line as the first line if (t && !t.left && !t.right) return ${t.val} as a guard condition; however, there is another test case that is not passing. The input is [0,0,0,0,null,null,0,null,null,null,0] and should return "0(0(0))(0()(0()(0)))". I am somewhat at a loss because it's only returning "". Any ideas as how to incorporate this test to pass?
Also, is anyone able to share an iterative solution. I tried using a stack, but wasn't able to work out the kinks in logic.
I made a minor change that may work. The if(val) line would evaluate to false if val is zero. So now it should evaluate the rest of the code if you pass in zero.
Why are you using an array and not a string? Because this answer to me feels like an unnecessarily over complicated solution. There's some hard coded conditions, and many data that can be simplified which takes up the memory.
The OP wanted help fixing the problem, not a full rewrite.
|
1

As user @Jonas Wilms mentioned, I don't see the need of using stack to this problem. I personally feel it is much more common to use a recursive approach (and it is more efficient / readable I think).

Here's the code

class TreeNode {
    constructor(val, left, right) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
    }
}

const tree2str = (tree) => {

    const dfs = (current) => {
        if (current === null) return ''

        let result = current.val.toString(); // in fact you don't need toString() here, but has a better readability

        const left = current.left;
        const right = current.right;

        if (left || right) {
            result += '(' + dfs(left) + ')';
        } 
        if (right) {
            result += '(' + dfs(right) + ')';
        }
        return result
    }
    return dfs(tree);
}

const tree1 = new TreeNode(1, new TreeNode(2, new TreeNode(4)), new TreeNode(3))
const tree2 = new TreeNode(1, new TreeNode(2, null, new TreeNode(4)), new TreeNode(3))
const tree3 = new TreeNode(1, new TreeNode(2, new TreeNode(3), new TreeNode(4)))

console.log(tree2str(tree1)) // "1(2(4))(3)"
console.log(tree2str(tree2)) // "1(2()(4))(3)"
console.log(tree2str(tree3)) // "1(2(3)(4))"

I tried to keep the code as simple as possible, and I'm pretty sure there are ways to improve this. Comment if any other input test doesn't work. It was a nice challenge. Cheers :)

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.