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:
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()after2is necessary to indicate the absence of a left child for2and the presence of a right child.
Constraints:
[1, 104].-1000 <= Node.val <= 1000This approach uses a recursive depth-first traversal starting from the root. For each node, construct the string representation by first adding the node's value. Then recursively obtain the string for the left and right subtrees. Handle empty parentheses carefully to meet problem constraints, particularly when a node has a right child but no left child.
The code defines a function tree2str that recursively traverses the tree. For each node, it checks if there's a need to include the left and/or right children in the string. If a right child exists without a left child, it includes an empty set of parentheses before the right child. Memory allocation is handled dynamically to accommodate the resultant string's size, given the constraints. The function returns the constructed string after processing all nodes.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes in the tree, as each node is visited once.
Space Complexity: O(h), where h is the height of the tree, due to the recursive call stack.
This approach leverages an iterative traversal using a stack to emulate the recursive call stack. This can be beneficial in languages without native recursion optimization or for learning alternative tree traversal methods. The stack helps manage nodes and their parents as we build the string representation iteratively.
The iterative Python solution uses a stack to manage tree traversal and construct the string. Each node's value is appended as we pop it from the stack. Special handling ensures proper insertion of parentheses to reflect tree structure accurately without recursion.
Time Complexity: O(n)
Space Complexity: O(n), as the stack can store every node.
| Approach | Complexity |
|---|---|
| Recursive Tree Traversal | Time Complexity: O(n), where n is the number of nodes in the tree, as each node is visited once. |
| Iterative Approach Using Stack | Time Complexity: O(n) |
How to solve (almost) any binary tree coding problem • Inside code • 224,586 views views
Watch 9 more video solutions →Practice Construct String from Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor