Construct String from Binary Tree

Medium
1902.

Construct String from Binary Tree

Construct String from Binary Tree is a medium coding problem on strings, depth-first search and trees, asked in Amazon, Microsoft and Meta interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string}
 */
var tree2str = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

  1. Hint 1

    The string is a preorder walk: the node's value, then the left subtree, then the right subtree.

  2. Hint 2

    Wrap each subtree's string in parentheses — the question is only when an empty subtree may be left out.

  3. 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

  1. Write the node's value.
  2. If the node has a left or a right child, write (, the left subtree's string (empty if there is none), and ).
  3. If the node has a right child, write (, the right subtree's string, and ).
  4. 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)