Construct String from Binary Tree solution and explanation
9 more videos on this problem
Construct String from Binary Tree - Leetcode 606 - PythonNeetCode · 10:00 · 42K views
leetcode 606. Construct String from Binary Treealgorithm everyday · 6:31 · 1K views
606. Construct String from Binary Tree | time-O(n) | Leetcode 606Aryan Mittal · 15:03 · 1K views
Leetcode 606 Construct String from Binary Tree | Tree TraversalCoding Decoded · 9:18 · 996 views
Construct String from Binary Tree - LeetCode #606 - Python, JavaScript, Java and C++CodingNinja · 7:44 · 712 views
Daily Leetcode #890: Sep 07, 2022 - 606. Construct String from Binary TreeProgramming Live with Larry · 9:57 · 436 views
Construct String from Binary Tree | Leetcode 606 | Amazon Google Facebook interview questionSuper Lazy Coder · 8:41 · 216 views
Leetcode 606 Construct String from Binary Tree - Amazon Interview QuestionAlgorithmicIQ · 9:42 · 192 views
Leetcode 606. Construct String from Binary Tree - RecursionCode-Yao · 11:33 · 173 views
Construct String from Binary Tree | Leetcode 606FahadLeetcode · 5:16 · 162 views
The problem
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:
- If a node has a left child, the value of the left child should be enclosed in parentheses immediately following the node's value.
- If a node has a right child, the value of the right child should also be enclosed in parentheses. The parentheses for the right child should follow those of the left child.
-
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:
- The number of nodes in the tree is in the range
[1, 104]. -1000 <= Node.val <= 1000
Approach overview
Problem Overview: Given a binary tree, build a string using preorder traversal where each node is written as value(left)(right). Empty parentheses are omitted unless needed to preserve the one‑to‑one mapping between the string and the tree structure.
Approach 1: Recursive Tree Traversal (DFS) (Time: O(n), Space: O(h))
The most natural solution uses preorder depth‑first traversal. Visit the current node, append its value to the result string, then recursively process the left and right children. The tricky rule: if a node has a right child but no left child, you must add an empty pair () to represent the missing left subtree. This preserves the structure so the tree can be uniquely reconstructed. Every node is processed once, giving O(n) time complexity. The recursion stack stores at most the tree height h, so the auxiliary space is O(h). This approach directly mirrors the definition of preorder traversal in a binary tree and is the most concise implementation.
Approach 2: Iterative Approach Using Stack (Time: O(n), Space: O(n))
An iterative version simulates DFS using an explicit stack. Push the root node and process nodes in preorder order while building the string. Track visited nodes so you know when to append closing parentheses. When pushing children, push the right child first and the left child second so the left subtree is processed first. If a node has a right child but no left child, explicitly append () before handling the right subtree. Each node enters and leaves the stack once, so the runtime remains O(n). The stack may hold multiple nodes simultaneously, leading to O(n) worst‑case space.
This problem mainly tests understanding of preorder depth‑first search and careful handling of string construction. Managing parentheses correctly is the core challenge rather than the traversal itself. The resulting algorithm builds the string incrementally while traversing the tree.
Recommended for interviews: The recursive DFS approach is what interviewers usually expect. It shows you understand preorder traversal and edge cases like missing left children when a right child exists. Mentioning the iterative stack version demonstrates deeper knowledge of how recursion can be simulated and how DFS works internally.
Approach 1: Recursive Tree Traversal
This 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.
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, t: TreeNode) -> str:
if not t:
return ""
result = str(t.val)
if t.left or t.right:
result += f'({self.tree2str(t.left)})'
if t.right:
result += f'({self.tree2str(t.right)})'
return resultclass TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public String tree2str(TreeNode t) {
if (t == null) return "";
String result = t.val + "";
if (t.left != null || t.right != null) {
result += "(" + tree2str(t.left) + ")";
}
if (t.right != null) {
result += "(" + tree2str(t.right) + ")";
}
return result;
}
}#include <string>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
std::string tree2str(TreeNode* t) {
if (!t) return "";
std::string result = std::to_string(t->val);
if (t->left || t->right) {
result += '(' + tree2str(t->left) + ')';
}
if (t->right) {
result += '(' + tree2str(t->right) + ')';
}
return result;
}
};function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
var tree2str = function(t) {
if (!t) return "";
let result = t.val.toString();
if (t.left || t.right) {
result += '(' + tree2str(t.left) + ')';
}
if (t.right) {
result += '(' + tree2str(t.right) + ')';
}
return result;
};#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
char *tree2str(TreeNode *t) {
if (!t) return "";
char *left = tree2str(t->left);
char *right = tree2str(t->right);
char *res = (char *)malloc(10000 * sizeof(char));
sprintf(res, "%d", t->val);
if (strlen(left) || strlen(right)) {
strcat(res, "(");
strcat(res, left);
strcat(res, ")");
}
if (strlen(right)) {
strcat(res, "(");
strcat(res, right);
strcat(res, ")");
}
free(left);
free(right);
return res;
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public string Tree2str(TreeNode t) {
if (t == null) return "";
string result = t.val.ToString();
if (t.left != null || t.right != null) {
result += "(" + Tree2str(t.left) + ")";
}
if (t.right != null) {
result += "(" + Tree2str(t.right) + ")";
}
return result;
}
}The Python solution defines a recursive function tree2str in a Solution class. The function converts each node value to a string and checks for children. Parentheses are used to ensure that the string reflects the tree's structure properly, handling empty pairs when necessary.
Time Complexity: O(n)
Space Complexity: O(h)
Approach 2: Iterative Approach Using 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.
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, t: TreeNode) -> str:
if not t:
return ""
stack = [(t, False)]
res = ""
while stack:
node, visited = stack.pop()
if visited:
if node == ")":
res += ")"
continue
if node == ")":
stack.append((")", True))
stack.append((node.right, False))
if node.left or node.right:
stack.append(("(", True))
stack.append((node.left, False))
stack.append(("(", True))
res += str(node.val)
else:
res += b_handle
return resThe 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 3: Default Approach
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function tree2str(root: TreeNode | null): string {
if (root == null) {
return '';
}
if (root.left == null && root.right == null) {
return `${root.val}`;
}
return `${root.val}(${root.left ? tree2str(root.left) : ''})${
root.right ? `(${tree2str(root.right)})` : ''
}`;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func tree2str(root *TreeNode) string {
if root == nil {
return ""
}
if root.Left == nil && root.Right == nil {
return strconv.Itoa(root.Val)
}
if root.Right == nil {
return strconv.Itoa(root.Val) + "(" + tree2str(root.Left) + ")"
}
return strconv.Itoa(root.Val) + "(" + tree2str(root.Left) + ")(" + tree2str(root.Right) + ")"
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, res: &mut String) {
if let Some(node) = root {
let node = node.borrow();
res.push_str(node.val.to_string().as_str());
if node.left.is_none() && node.right.is_none() {
return;
}
res.push('(');
if node.left.is_some() {
Self::dfs(&node.left, res);
}
res.push(')');
if node.right.is_some() {
res.push('(');
Self::dfs(&node.right, res);
res.push(')');
}
}
}
pub fn tree2str(root: Option<Rc<RefCell<TreeNode>>>) -> String {
let mut res = String::new();
Self::dfs(&root, &mut res);
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Tree Traversal | Time Complexity: O(n) |
| Iterative Approach Using Stack | Time Complexity: O(n) |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Tree Traversal (DFS) | O(n) | O(h) | Best general solution. Clean and concise when recursion depth is manageable. |
| Iterative DFS Using Stack | O(n) | O(n) | Useful when avoiding recursion or when stack‑based DFS is preferred. |
Frequently asked questions
Is Construct String from Binary Tree easy or hard?
Construct String from Binary Tree is considered a Medium difficulty problem. The traversal itself is straightforward, but correctly handling the parentheses rules—especially when the left child is missing but the right child exists—adds the main challenge.
Construct String from Binary Tree Python/Java solution
In Python or Java, implement a preorder DFS function that returns a string for each subtree. Append the node value, recursively build the left and right parts, and include parentheses according to the problem rules. Both implementations run in O(n) time with O(h) recursion stack space.
How to solve Construct String from Binary Tree in O(n)?
Perform a preorder depth-first traversal of the tree. Append the current node value to the result string, recursively process the left subtree, and then the right subtree. Insert parentheses around children and include an empty pair when the left child is missing but the right child exists. This processes each node once, achieving O(n) time.
What is the best approach for Construct String from Binary Tree?
The recursive preorder DFS approach is the most efficient and easiest to implement. Traverse the node, then its left and right children while building the string. Add empty parentheses only when a node has a right child but no left child. This solution runs in O(n) time and O(h) space where h is the tree height.
Is Construct String from Binary Tree asked at Google/Amazon/Meta?
Binary tree traversal and string construction problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants of this question test understanding of preorder traversal, recursion, and careful handling of edge cases in tree serialization.
What data structure is used in Construct String from Binary Tree?
The core data structure is a binary tree. The algorithm typically uses recursion (call stack) or an explicit stack to perform depth‑first search while constructing the resulting string representation.
What is the time complexity of Construct String from Binary Tree?
The time complexity is O(n) because each node in the binary tree is visited exactly once during the preorder traversal. String construction also occurs once per node, so the overall work grows linearly with the number of nodes.