Construct String from Binary Tree
Medium · Graphs · Explanation and code example
Iterative DFS
How it works
We can convert the recursive approach to iterative using an explicit stack. The challenge is knowing when we have finished processing a node's subtrees so we can add the closing parenthesis. We track the last visited node to determine whether we are returning from the right subtree.
Steps
- Use a stack for traversal and track the last visited node.
- While current node exists or stack is not empty:
- If current exists, append
"(val", handle missing left child if right exists, push to stack, move to left child. - Otherwise, peek at the stack top:
- If right child exists and was not last visited, move to right child.
- Otherwise, pop the node, append
")", mark it as last visited.
- If current exists, append
- Remove the outer parentheses from the result and return.
Complexity
- Time complexity:
O(n) - Space complexity:
O(n)
Things to watch for
Omitting Empty Parentheses for Missing Left Child
When only the right child exists, you must include empty parentheses () for the missing left child to preserve tree structure. Without this, the right child would be incorrectly interpreted as the left child during reconstruction.
Adding Unnecessary Parentheses for Missing Right Child
When only the left child exists, you should NOT add empty parentheses for the missing right child. The problem specifically states that empty parentheses for missing right children should be omitted since they don't affect tree reconstruction.
Python code example
from typing import Optional
# Definition for a binary tree node.
# 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, root: Optional[TreeNode]) -> str:
if not root:
return ""
res = []
stack = []
last_visited = None
cur = root
while cur or stack:
if cur:
res.append(f"({cur.val}")
if not cur.left and cur.right:
res.append("()")
stack.append(cur)
cur = cur.left
else:
top = stack[-1]
if top.right and last_visited != top.right:
cur = top.right
else:
stack.pop()
res.append(")")
last_visited = top
return "".join(res)[1:-1]
C++ code example
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
string tree2str(TreeNode* root) {
if (!root) {
return "";
}
string res;
stack<TreeNode*> stack;
TreeNode* lastVisited = nullptr;
TreeNode* cur = root;
while (cur || !stack.empty()) {
if (cur) {
res += "(" + to_string(cur->val);
if (!cur->left && cur->right) {
res += "()";
}
stack.push(cur);
cur = cur->left;
} else {
TreeNode* top = stack.top();
if (top->right && lastVisited != top->right) {
cur = top->right;
} else {
stack.pop();
res += ")";
lastVisited = top;
}
}
}
return res.substr(1, res.size() - 2);
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.