Construct String from Binary Tree

Problem Statement

The challenge involves generating a string representation of a binary tree provided the root node. This task requires following a preorder traversal method, where each node's value is first noted followed by its descendents. The nodes must be represented as integers, and the structure of the tree should be conveyed using parentheses to enclose child nodes values.

For a detailed explanation:

• Node Representation: Each node's value is directly included in the output string as an integer.
• Parentheses for Children: When a node has children, the child values are enclosed in parentheses:
  • The left child’s value (if present) should be immediately next to the parent value and within parentheses.
  • The right child’s value (if present) should follow, enclosed in its own set of parentheses directly after the left child's parentheses. If the left child is not present but the right is, then an empty set of parentheses should precede the right child's value.
• Omitting Empty Parentheses: To avoid redundancy and keep the output clean, pairs of empty parentheses are not included unless they denote the absence of a left child when there's a right child. This specific structure allows for an accurate mapping back to the tree structure from the string representation.

Examples

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 `()` after `2` is necessary to indicate the absence of a left child for `2` and 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 and Intuition

To solve this problem, understand the following from the given examples and constraints:

• The approach must ensure correctness in displaying children with required parentheses. If a node has:

  1. Both children, it's represented as node_val(left_child)(right_child).
  2. Only a left child, without unnecessary parentheses for the non-existent right child.
  3. Only a right child, indicate this with a pair of empty parentheses for the missing left child followed by the right child's value in another set of parentheses.
  4. No children, just the node's value is used without any parentheses.

• In terms of traversal:

  1. Begin with the root and examine its children.
  2. If a node has children, recursively apply the same logic first to the left child followed by the right child. This reflects the preorder traversal (root-left-right).
  3. Conditional checks are crucial to decide where and whether to add parentheses, especially to determine if the empty parentheses are needed (only when there’s a right child and no left child).

By closely following these rules and intuitively linking each node with its respective children through recursion and conditional structuring, the desired string format of the binary tree can be accurately constructed. This approach ensures that all necessary details are depicted without superfluous characters, maintaining a true representation of the tree structure.

Solutions

public class Solution {
    public String binaryTreeToString(TreeNode node) {
        if (node == null)
            return "";
        Stack<TreeNode> nodeStack = new Stack<>();
        nodeStack.push(node);
        HashSet<TreeNode> seenNodes = new HashSet<>();
        StringBuilder result = new StringBuilder();
        while (!nodeStack.isEmpty()) {
            node = nodeStack.peek();
            if (seenNodes.contains(node)) {
                nodeStack.pop();
                result.append(")");
            } else {
                seenNodes.add(node);
                result.append("(" + node.val);
                if (node.left == null && node.right != null)
                    result.append("()");
                if (node.right != null)
                    nodeStack.push(node.right);
                if (node.left != null)
                    nodeStack.push(node.left);
            }
        }
        return result.substring(1, result.length() - 1);
    }
}