Construct String From Binary Tree - Leetcode Solution

Problem Statement:

Given the root of a binary tree, construct a string consisting of parenthesis and integers, where the parenthesis denote the subtrees in a way similar to LeetCode 606: Construct Binary Tree from String.

In this representation, a node is represented by its value and its subtrees are represented by parenthesis containing the representation of the subtree.

The left subtree is represented by appending the string "()" to the representation of the parent node, and the right subtree is represented by appending the string "(right_subtree)", where right_subtree is the representation of the right subtree.

If the right subtree is empty, it is not represented.

Examples:

Example 1:

Input: root = [1,2,3,4] Output: "1(2(4))(3)"

Explanation: The tree is the following:

  1
/   \

2 3 / 4

We can see that the string representation of the tree is "1(2(4))(3)".

Example 2:

Input: root = [1,2,3,null,4] Output: "1(2()(4))(3)"

Explanation: The tree is the following:

  1
/   \

2 3
4

We can see that the string representation of the tree is "1(2()(4))(3)".

Approach:

We can solve this problem recursively. We will define a helper function that will take the root node as input and return the string representation of the subtree rooted at the given node. We can then use this helper function to construct the string representation of the entire tree, starting from the root node.

The helper function will do the following:

• If the root node is None, we will return an empty string.
• If the root node has no left or right subtree, we will return a string representation of the root node's value.
• If the root node has a left subtree but no right subtree, we will return the string representation of the root node's value followed by the string representation of the left subtree surrounded by parentheses.
• If the root node has a right subtree but no left subtree, we will return the string representation of the root node's value followed by "()" and the string representation of the right subtree in parentheses.
• If the root node has both a left and right subtree, we will return the string representation of the root node's value followed by the string representation of the left subtree in parentheses, followed by the string representation of the right subtree in parentheses.

Algorithm:

1. Define a function called tree2str which will take root as argument.
2. Check if the root is null. If root is null return an empty string.
3. If the root has left subtree and also if the root has right subtree, call the tree2str function recursively for left subtree and right subtree and concatenate the results.
4. If the root has no left subtree but has right subtree call tree2str function recursively for right subtree and concatenate the result along with "()" and the value of root.
5. If the root has left subtree but no right subtree call tree2str function recursively for left subtree and concatenate the result along with "()" and the value of root.
6. If no children then return the value string.
7. Return the final result.

Time Complexity:

The time complexity is O(N), where N is the number of nodes in the tree. This is because we visit each node exactly once in the recursive function.

Space Complexity:

The space complexity is O(H), where H is the height of the tree. We use the call stack to keep track of the recursive calls, which takes O(H) space. Since this is a binary tree, the worst-case scenario is when the tree is completely unbalanced, in which case the height is equal to the number of nodes, and the space complexity becomes O(N).

Solution:

class Solution: def tree2str(self, root: Optional[TreeNode]) -> str: if not root: return "" if not root.left and not root.right: return str(root.val) if not root.right: return str(root.val) + "(" + self.tree2str(root.left) + ")" return str(root.val) + "(" + self.tree2str(root.left) + ")" + "(" + self.tree2str(root.right) + ")"

Time Complexity: O(N) Space Complexity: O(H)

1