Log inSign up
easyleetcodeNot Started

Construct String from Binary Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

Given the root of a binary tree, construct a string consisting of parenthesis and integers from a binary tree with the preorder traversal way, and return it.

Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree: 1. If both left and right children are null: omit parentheses for both. 2. If left child is null but right child exists: keep empty parentheses for left "()" to preserve distinction from having only a left child. 3. If left child exists and right child is null: omit parentheses for right child.

Example 1 · Example 1: Left Child with Grandchild:

Input: root = [1, 2, 3, 4] Tree: 1 / \ 2 3 / 4
Output: "1(2(4))(3)"
Explanation: Right child of 2 is null so omitted. Left and right of 4 are null so omitted. Right child 3 is present.

Example 2 · Example 2: Left Child Null with Right Child:

Input: root = [1, 2, 3, null, 4] Tree: 1 / \ 2 3 \ 4
Output: "1(2()(4))(3)"
Explanation: Node 2 has no left child, but has a right child (4). An empty () must be included for the left child to indicate 4 is on the right.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why empty parentheses () are required when a node has a right child but no left child.
  • Apply preorder DFS to string construction.
  • Optimize string concatenation using StringBuilder or in-place accumulation.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Tree serialization with parentheses.
  • Preorder traversal string representation.
  • Omit redundant empty parentheses.

Algorithmic Decision Tree:

  • If root == null -> return ''.
  • res = String(root.val).
  • If left != null || right != null -> res += ( + tree2str(left) + ).
  • If right != null -> res += ( + tree2str(right) + ).

Connected Patterns:

Serialize and Deserialize Binary TreeBinary Tree PathsFind Duplicate Subtrees

1. Unconditional Parentheses with Regex Replacement

Intuition

Output node.val(left)(right) for all nodes. Clean up empty () using string replacements.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Base recursion creates string with full parenthesis pairing.
  2. Step 2: Clean trailing empty parentheses where legal.
  3. Step 3: Return cleaned string.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 string tree2str(TreeNode* root) {
10 if (!root) return "";
11 string left = tree2str(root->left);
12 string right = tree2str(root->right);
13 if (left.empty() && right.empty()) return to_string(root->val);
14 if (right.empty()) return to_string(root->val) + "(" + left + ")";
15 return to_string(root->val) + "(" + left + ")(" + right + ")";
16 }
17};
18
19int main() {
20 // Sample driver execution
21 cout << "Execution completed successfully." << endl;
22 return 0;
23}
24

Time & Space Complexity

  • Time complexity: O(n^2) — String manipulations and regex replacements create intermediate strings.
  • Space complexity: O(n^2) — Regex matching copies strings repeatedly.

2. Iterative DFS with Stack and Visited Set

Intuition

Use an explicit stack. Push node and track visited status to append ( on entry and ) on exit.

When to apply: When avoiding recursive call stacks.

Algorithm

  1. Step 1: Use a stack of TreeNode* and a visited set.
  2. Step 2: Push root. When a node is popped for the first time, append value and push closing marker.
  3. Step 3: Enqueue right then left children.
  4. Step 4: Return accumulated string.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 string tree2str(TreeNode* root) {
10 if (!root) return "";
11 string res = "";
12 stack<TreeNode*> st;
13 st.push(root);
14 unordered_set<TreeNode*> visited;
15 while (!st.empty()) {
16 TreeNode* cur = st.top();
17 if (visited.count(cur)) {
18 st.pop();
19 res += ")";
20 } else {
21 visited.insert(cur);
22 res += "(" + to_string(cur->val);
23 if (!cur->left && cur->right) res += "()";
24 if (cur->right) st.push(cur->right);
25 if (cur->left) st.push(cur->left);
26 }
27 }
28 return res.substr(1, res.size() - 2);
29 }
30};
31
32int main() {
33 // Sample driver execution
34 cout << "Execution completed successfully." << endl;
35 return 0;
36}
37

Time & Space Complexity

  • Time complexity: O(n) — Each node pushed and popped twice from stack.
  • Space complexity: O(n) — Explicit stack and visited set take O(n) space.

3. Canonical Recursive Preorder DFS with In-Place String Accumulation

Intuition

Append root.val to result. If left exists or right exists, wrap left traversal in parentheses (e.g. (tree2str(left))). If right exists, wrap right traversal in parentheses. Never create empty parentheses for missing right children.

When to apply: Optimal gold-standard solution.

Algorithm

  1. Step 1: If root == null return.
  2. Step 2: Append root.val to string buffer.
  3. Step 3: If root.left != null || root.right != null: append (, recurse on left, append ).
  4. Step 4: If root.right != null: append (, recurse on right, append ).
  5. Step 5: Return buffer string.

String Construction Trace for root = [1, 2, 3, null, 4]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Start at root 1
Visual state
Values and pointers at this exact step
tree
Root
1
L
2
R
3

Node order shown; add connections to display explicit tree edges.

root: 1
Check / comparison
Root val: '1'
Decision / next transition
Add '1'. Recurse on left child 2.
Why this step matters

Step 1: Start at root 1. String begins with 1. Recurse into left child 2.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void dfs(TreeNode* root, string& res) {
10 if (!root) return;
11 res += to_string(root->val);
12 if (root->left || root->right) {
13 res += "(";
14 dfs(root->left, res);
15 res += ")";
16 }
17 if (root->right) {
18 res += "(";
19 dfs(root->right, res);
20 res += ")";
21 }
22 }
23 string tree2str(TreeNode* root) {
24 string res = "";
25 dfs(root, res);
26 return res;
27 }
28};
29
30int main() {
31 // Sample driver execution
32 cout << "Execution completed successfully." << endl;
33 return 0;
34}
35

Time & Space Complexity

  • Time complexity: O(n) — Every node visited once; in-place buffer prevents string copy overhead.
  • Space complexity: O(h) — Call stack bounded by tree height h.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Conditional Return StringsO(n)O(n)Return subtree string combinations conditionally.String concatenations.
2.Iterative DFS with StackO(n)O(n)Explicit stack tracking entry and exit to append parens.Stack overhead.
3.Canonical Preorder DFS with In-Place BufferOptimalO(n)O(h)Append directly into a string buffer in preorder fashion.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Single node: root = [1] -> 1.
  • Left child only: root = [1, 2] -> 1(2).
  • Right child only: root = [1, null, 2] -> 1()(2) (empty () required for left!).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Point out Example 2: why 1()(3) cannot be simplified to 1(3). Without (), 1(3) would mean 3 is the left child of 1, breaking one-to-one mapping.
  2. Use StringBuilder in Java / string appending in C++ to avoid unnecessary string copies.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does node with left == null and right != null require an empty pair of parentheses ()?

Back to DSA Sheet