#606

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Construct String from Binary Tree

Given a binary tree, construct a string representation based on preorder traversal while adhering to specific formatting rules.

string tree depth first search binary tree

Problem Statement

Given the root of a binary tree, your task is to create a string representation of the tree following specific formatting rules. The tree's string representation should use preorder traversal, and each node should be formatted as 'NodeValue(LeftSubtree)(RightSubtree)', omitting empty parentheses where either subtree is missing. For nodes with no children, just 'NodeValue' is sufficient.

For example, consider the binary tree represented by root = [1,2,3,4]. The correct output string is '1(2(4))(3)', where empty parentheses are omitted. Similarly, a tree with root = [1,2,3,null,4] should output '1(2()(4))(3)', as it explicitly shows the absence of a left child for node 2 with '()'.

Examples

Example 1

Input: root = [1,2,3,4]

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

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)"

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 Approach

Preorder Traversal with Recursion

Start by performing a recursive preorder traversal of the binary tree. At each node, construct its string representation based on its left and right children. If a child node is absent, omit the empty parentheses.

Edge Case Handling

Handle edge cases where a node has one child or no children at all. For single-child nodes, ensure that the output reflects the presence of the existing child without adding unnecessary parentheses for the absent child.

Efficient String Construction

Use a helper function to efficiently build and concatenate strings as you traverse the tree. Consider using StringBuilder or equivalent to avoid performance issues when dealing with large trees.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used for traversal, but generally it is O(N), where N is the number of nodes in the tree. The space complexity can vary based on the recursive stack depth and string construction, often O(H) where H is the height of the tree in the worst case, or O(N) for a fully unbalanced tree.

What Interviewers Usually Probe

Candidate correctly identifies the pattern of binary tree traversal and can apply recursion for string construction.
Candidate handles edge cases involving null children and correctly omits empty parentheses.
Candidate demonstrates awareness of efficient string construction to avoid performance bottlenecks.

Common Pitfalls or Variants

Common pitfalls

Failing to handle null children correctly by not omitting empty parentheses or incorrectly representing them.
Using inefficient string concatenation methods that could lead to performance issues in large trees.
Not properly formatting the output string when there is a node with only one child.

Follow-up variants

Handle a binary tree that contains only left or right children, ensuring correct output formatting.
Optimize the approach for very large trees, considering both time and space efficiency.
Modify the problem to return the result in a different format, such as JSON or a list representation.

FAQ

What is the most common mistake when solving the Construct String from Binary Tree problem?

The most common mistake is incorrectly handling null children, either by not omitting the empty parentheses or by misrepresenting them in the output.

How does recursion help in solving Construct String from Binary Tree?

Recursion helps by naturally performing preorder traversal, allowing us to construct each node's string representation in a straightforward manner.

Why do we omit empty parentheses in the Construct String from Binary Tree problem?

Empty parentheses are omitted to simplify the string and correctly represent only existing child nodes, maintaining clarity in the tree's structure.

What is the time complexity of the Construct String from Binary Tree problem?

The time complexity is generally O(N), where N is the number of nodes in the tree, since we visit each node exactly once during traversal.

How can we optimize the Construct String from Binary Tree solution for large trees?

Optimizing for large trees involves careful string construction to minimize overhead, and using efficient methods like StringBuilder or equivalent to avoid repeated concatenation.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
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)

Continue Practicing

#449 serialize and deserialize bst #297 serialize and deserialize binary tree #257 binary tree paths