Construct String from Binary Tree

easy tree dfs string

Problem

Given the root of a binary tree, construct a preorder string of the form "val(left)(right)". Omit empty parenthesis pairs that don't affect the one-to-one mapping between the string and the tree — specifically, drop the empty right subtree's "()", but keep an empty left subtree's "()" whenever the right exists.

Inputroot = [1, 2, 3, 4]

Output"1(2(4))(3)"

The leaf 4 is the left child of 2; 2's right is empty so its "()" is dropped.

tree (level-order; "null" for missing)

def tree2str(root):
    if not root:
        return ""
    s = str(root.val)
    if root.left or root.right:
        s += "(" + tree2str(root.left) + ")"
    if root.right:
        s += "(" + tree2str(root.right) + ")"
    return s

function tree2str(root) {
  if (!root) return "";
  let s = String(root.val);
  if (root.left || root.right) s += "(" + tree2str(root.left) + ")";
  if (root.right) s += "(" + tree2str(root.right) + ")";
  return s;
}

class Solution {
    public String tree2str(TreeNode root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        sb.append(root.val);
        if (root.left != null || root.right != null) sb.append("(").append(tree2str(root.left)).append(")");
        if (root.right != null) sb.append("(").append(tree2str(root.right)).append(")");
        return sb.toString();
    }
}

string tree2str(TreeNode* root) {
    if (!root) return "";
    string s = to_string(root->val);
    if (root->left || root->right) s += "(" + tree2str(root->left) + ")";
    if (root->right) s += "(" + tree2str(root->right) + ")";
    return s;
}

Explanation

We turn a tree back into a string of the form val(left)(right) using a preorder DFS: write the node's value first, then recursively wrap each child in parentheses. The only subtlety is knowing when an empty pair of parentheses can be dropped.

For each node we always print its value. We add the left group (...) whenever the node has either a left or a right child, because if the right child exists we still need a placeholder so positions stay unambiguous.

We add the right group only when a right child actually exists. A trailing empty right group would be meaningless, so omitting it keeps the string short while still mapping uniquely back to the tree.

Example: tree [1, 2, 3, 4] (root 1, left 2 with its own left child 4, right 3). We write 1, then (2(4)) for the left subtree, then (3) for the right, giving 1(2(4))(3). Node 2's empty right child is dropped, but its left child 4 is kept.

Because every node is visited once and we only emit parentheses we truly need, the result is a compact, reversible encoding.

Time: O(n) Space: O(h) recursion stack