Construct String from Binary Tree — Problem & Solution
Construct String from Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Construct String from Binary Tree is a medium coding problem on strings, depth-first search and trees, asked in Amazon, Microsoft and Meta interviews.
- Difficulty: Medium
- Topics: Strings, Depth-First Search, Trees
- Asked at: Amazon, Microsoft, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, write it as a string in preorder: a node is its value, followed by its left subtree in parentheses, followed by its right subtree in parentheses.
Leave out every pair of empty parentheses that is not needed to read the tree back unambiguously:
- a node with no children is just its value;
- a node with only a left child drops the empty pair for its right child;
- a node with only a right child keeps an empty pair
()for its missing left child.
Example 1
Input: root = [1,2,3,4]
Output: 1(2(4))(3)
Explanation: 2 has only a left child, so its empty right pair is dropped: `1(2(4))(3)`.
Example 2
Input: root = [1,2,3,null,4]
Output: 1(2()(4))(3)
Explanation: 2 has only a right child; its empty left pair `()` must stay, or 4 would read as a left child.
Example 3
Input: root = [-5,null,7]
Output: -5()(7)
Explanation: Negative values are written with their sign; the empty left pair stays because a right child follows.
Constraints
1 <= number of nodes <= 10^4-1000 <= Node.val <= 1000
Hints for Construct String from Binary Tree
Hint 1
The string is a preorder walk: the node's value, then the left subtree, then the right subtree.
Hint 2
Wrap each subtree's string in parentheses — the question is only when an empty subtree may be left out.
Hint 3
Write the left pair whenever the node has any child (it is
()when the left child is missing), and the right pair only when there is a right child.
How to solve Construct String from Binary Tree
Emit the tree in preorder, putting each subtree in parentheses, and keep an empty pair only where dropping it would let a right child be read as a left one.
Approach
- Write the node's value.
- If the node has a left or a right child, write
(, the left subtree's string (empty if there is none), and). - If the node has a right child, write
(, the right subtree's string, and). - Build the string in one buffer by recursing from the root.
Why it works
A reader takes the first parenthesised group after a value as the left subtree and the second as the right. A missing right child leaves no second group, which reads correctly; a missing left child before a present right child needs the placeholder (), or the right subtree would occupy the first group. Leaves need neither.
Complexity
- Time —
O(n) - Space —
O(n) for the output and O(h) for the recursion
Pitfalls
- Dropping
()before a right child changes the tree the string describes. - Concatenating strings returned by every call can cost O(n^2) on a chain; append to one shared buffer.
Reference solution
Python
from typing import Optional
def tree2str(root: Optional[TreeNode]) -> str:
out = []
def walk(node):
out.append(str(node.val))
if node.left or node.right:
out.append("(")
if node.left:
walk(node.left)
out.append(")")
if node.right:
out.append("(")
walk(node.right)
out.append(")")
if root is not None:
walk(root)
return "".join(out)Java
public static String tree2str(TreeNode root) {
StringBuilder sb = new StringBuilder();
if (root != null) strWalk(root, sb);
return sb.toString();
}
static void strWalk(TreeNode node, StringBuilder sb) {
sb.append(node.val);
if (node.left != null || node.right != null) {
sb.append('(');
if (node.left != null) strWalk(node.left, sb);
sb.append(')');
}
if (node.right != null) {
sb.append('(');
strWalk(node.right, sb);
sb.append(')');
}
}C++
void strWalk(TreeNode* node, string& out);
string tree2str(TreeNode* root) {
string out;
if (root) strWalk(root, out);
return out;
}
void strWalk(TreeNode* node, string& out) {
out += to_string(node->val);
if (node->left || node->right) {
out += '(';
if (node->left) strWalk(node->left, out);
out += ')';
}
if (node->right) {
out += '(';
strWalk(node->right, out);
out += ')';
}
}JavaScript
var tree2str = function(root) {
var out = [];
if (root !== null) strWalk(root, out);
return out.join("");
};
var strWalk = function(node, out) {
out.push(String(node.val));
if (node.left !== null || node.right !== null) {
out.push("(");
if (node.left !== null) strWalk(node.left, out);
out.push(")");
}
if (node.right !== null) {
out.push("(");
strWalk(node.right, out);
out.push(")");
}
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Depth-First Search (DFS)