606. Construct String from Binary Tree
Model: qwen2.5-coder:14b
Topics: String,Tree
FAANG asked: 0
Acceptance rate: 55.8%
Problem Breakdown
The problem requires constructing a string representation of a binary tree using preorder traversal (root-left-right). Each node in the tree should be represented by its value enclosed in parentheses. Null nodes are represented by empty parentheses ”()”. The goal is to omit unnecessary empty parenthesis pairs that do not affect the one-to-one mapping between the string and the original binary tree.
Inputs:
- A binary tree with integer values.
- Nodes can have zero, one, or two children (left and right).
Outputs:
- A string representing the binary tree in preorder traversal format.
Implicit Constraints/Edge Cases:
- The tree can be empty.
- Nodes can have only left or only right child.
- The tree can be unbalanced.
Intuition
A brute-force approach would involve recursively traversing the tree and appending strings for each node, including handling null nodes explicitly. However, this approach might lead to unnecessary complexity in managing parentheses and ensuring correct formatting.
The key insight is to use a recursive function that constructs the string by appending the current node’s value and recursively processing its left and right children. The function should handle null nodes by returning an empty string, which will be correctly formatted by the parent node’s handling of its children.
Approach
- Define a helper function
constructthat takes a tree node as input. - If the node is
None, return an empty string. - Initialize the result with the current node’s value.
- Recursively call
constructon the left child:- If the left child exists, append its string representation enclosed in parentheses.
- If only the right child exists (and not the left), append ”()” to indicate a null left child followed by the right child’s string representation.
- Recursively call
constructon the right child and append its string representation if it exists. - Return the constructed string for the current node.
Complexity Analysis
- Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once.
- Space Complexity: O(h), where h is the height of the tree. This accounts for the recursion stack. In the worst case (unbalanced tree), this can be O(n).
Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def tree2str(root: TreeNode) -> str:
if not root:
return ""
def construct(node):
if not node:
return ""
result = str(node.val)
# Process left child
if node.left:
result += "(" + construct(node.left) + ")"
elif node.right:
result += "()"
# Process right child
if node.right:
result += "(" + construct(node.right) + ")"
return result
return construct(root)
Edge Cases Handled
- Empty Tree: If the input tree is empty (
rootisNone), the function returns an empty string. - Single Node Tree: If the tree has only one node, the function returns just that node’s value as a string.
- Nodes with Only Left or Right Child: The function correctly handles cases where a node has only a left child or only a right child by appending ”()” for missing children to maintain the correct mapping.
- Unbalanced Tree: The recursive approach naturally handles unbalanced trees without additional complexity.