Construct String from Binary Tree

Photo by Sarra Marzguioui on Unsplash

Today I picked up a random problem from Leetcode, as an easy exercise for a rainy Sunday. And, spoiler alert, it’s about one of my most favorite topics — Tree. So here we go.

Description

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.

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

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

Source: Leetcode

Some thoughts

One thing I have learned over the past few months doing Leetcode is that, when we see Tree, we think about recursion. Of course, it's not necessarily always be the most optimal solution but it’s a good start. Another thing I’ve learned is that recursion is NOT my cup of tea. I am not good at it. Somehow my brain is not wired for this kind of thinking. I know, I mentioned it before in another blog that practice makes perfect. So here I am trying to solve another recursive problem.

Back to the main point, when we think about recursion, we need…

• A base case — a condition so the function will stop calling itself all over again.
• A recursive case — a condition for the function to call itself until reaches the base case.

For this example, the function stops calling itself when there are no more nodes to explore.

To begin with, we will start with the TreeNode class that holds some attributes:

• the value of the node (val)
• the node of the left branch (left) and the right branch (right)
• a constructor
• plus a toString() method for easier reading, nothing fancy.

public static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
               "val=" + val +
               ", left=" + left +
               ", right=" + right +
               '}';
    }
}

• An empty method called treeToStr() takes a node as a parameter.

private String treeToStr(TreeNode t) {
}

Next, we’re gonna look at some base cases.

• In case the node is null, returns an empty string “ ”.

if (t == null) return "";

• In case the left and right nodes are null, we no longer need to traverse the tree, so we return the value of the node.

if (t.left == null && t.right == null) return t.val + "";

Here comes the tricky part. According to the problem statement, we “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”.

Consider this example:

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

Given Node(1) as the root of the tree, here if we don’t add empty parentheses of the left node (Node(2).left) to the final string, we won’t know that Node(4) is the right node of Node(2). So if the answer is 1(2(4))(3), Node(4) would be the left node of Node(2), which is not correct. It’s something to keep in mind when we construct the algorithm.

Recursion is all about delegation. If the current function with the current parameter can’t solve the problem yet, call that function again with an updated parameter until it reaches the base case, something that can be solved easily. For instance, to construct a string from the root node Node(1), we must solve the Node(1).left and Node(1).right. Moreover, because both the left and right nodes are not null, as well as we must traverse the tree in a preOrder way, we must keep traverse the left nodes until there is no more node to discover, then we go to the right nodes. Along the way, we will add parentheses to the new string as well.

Proposed Solution

I want to emphasize a little bit here. Like I have mentioned before, in case the left node is null, we still need to append empty parentheses to the final string. Nevertheless, if the right node is null, we don’t need to do so because it’s invalid.

if (t.right == null) {
    return t.val + "(" + tree2str(t.left) + ")";
}

I hope that my explanation is clear enough. Otherwise, I am more than happy to get constructive feedback from you guys.

Happy coding!