{x}
blog image

Construct String from Binary Tree

Given the root node of a binary tree, your task is to create a string representation of the tree following a specific set of formatting rules. The representation should be based on a preorder traversal of the binary tree and must adhere to the following guidelines:

  • Node Representation: Each node in the tree should be represented by its integer value.

  • Parentheses for Children: If a node has at least one child (either left or right), its children should be represented inside parentheses. Specifically:

    • If a node has a left child, the value of the left child should be enclosed in parentheses immediately following the node's value.
    • If a node has a right child, the value of the right child should also be enclosed in parentheses. The parentheses for the right child should follow those of the left child.

  • Omitting Empty Parentheses: Any empty parentheses pairs (i.e., ()) should be omitted from the final string representation of the tree, with one specific exception: when a node has a right child but no left child. In such cases, you must include an empty pair of parentheses to indicate the absence of the left child. This ensures that the one-to-one mapping between the string representation and the original binary tree structure is maintained.

    In summary, empty parentheses pairs should be omitted when a node has only a left child or no children. However, when a node has a right child but no left child, an empty pair of parentheses must precede the representation of the right child to reflect the tree's structure accurately.

 

Example 1:

Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the empty parenthesis pairs. And it will be "1(2(4))(3)".

Example 2:

Input: root = [1,2,3,null,4]
Output: "1(2()(4))(3)"
Explanation: Almost the same as the first example, except the () after 2 is necessary to indicate the absence of a left child for 2 and the presence of a right child.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -1000 <= Node.val <= 1000

Solution Explanation

This problem requires constructing a string representation of a binary tree using a preorder traversal. The key challenge lies in handling the parentheses to accurately represent the tree structure while omitting unnecessary empty parentheses.

The solution uses a recursive depth-first search (DFS) approach. The function dfs (or its equivalent in different languages) recursively traverses the tree. The base case is when a node is null (or None), in which case an empty string is returned.

The core logic handles three scenarios:

  1. Leaf Node: If the node is a leaf (no left or right children), its value is directly converted to a string and returned.

  2. Node with Only Left Child: If a node only has a left child, the string representation becomes node_value(left_subtree_representation).

  3. Node with Left and/or Right Child: If a node has both left and right children, or only a right child, the representation is node_value(left_subtree_representation)(right_subtree_representation). Crucially, even if the left subtree is empty, () is included to preserve structural information if a right subtree exists.

Time Complexity Analysis:

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

Space Complexity Analysis:

The space complexity depends on the recursion depth, which is at most the height (h) of the tree. In the worst case (a skewed tree), the height can be equal to N, resulting in O(N) space complexity. In the best case (a balanced tree), the height is log₂(N), leading to O(log₂(N)) space complexity. Therefore, the space complexity is O(H) or O(N) in the worst case where H is the height of the tree.

Code Explanation (Python):

The Python solution exemplifies the approach clearly:

class Solution:
    def tree2str(self, root: Optional[TreeNode]) -> str:
        def dfs(root):
            if root is None:
                return ''
            if root.left is None and root.right is None:
                return str(root.val)
            if root.right is None:
                return f'{root.val}({dfs(root.left)})'
            return f'{root.val}({dfs(root.left)})({dfs(root.right)})'
 
        return dfs(root)

The inner function dfs recursively constructs the string representation. The conditional statements carefully handle each case, ensuring that the parentheses are correctly placed and empty parentheses are omitted where appropriate except when a node has a right child but no left child.

The other language solutions (Java, C++, Go, TypeScript, Rust) follow the same logic, adapting the syntax and data structures according to the respective language's conventions. The core recursive DFS strategy remains the same across all solutions.