606. Construct String from Binary Tree


Problem Description

The problem provides a binary tree (where each node has at most two children) and asks you to transform it into a specific string format based on the rules of preorder traversal. This traversal visits the root, followed by the left subtree, and then the right subtree. As you navigate the tree, the goal is to create a string that represents the tree structure via parentheses. Each node's value must be captured in the string, and for non-leaf nodes, its children should be represented inside parentheses. Importantly, if a node has an empty right child, you still need to use a pair of parentheses to indicate the left child, but you are not required to include parentheses for an empty left child if there is also no right child. The challenge is to omit all unnecessary empty parentheses pairs to avoid redundancy in the resulting string.

Intuition

The solution is grounded in the idea of depth-first search (DFS), which explores as far as possible along each branch before backtracking. This concept is perfect for the preorder traversal required by the problem. To implement the DFS, you recursively visit nodes, starting from the root down to the leaves, while building the string representation as per the rules.

Here's an intuitive breakdown of the approach:

  • If the current node is None (meaning you've reached a place without a child), return an empty string since you don't need to add anything to the string.

  • If the current node is a leaf node (it has no left or right child), return the node's value as a string, since no parentheses are needed.

  • If the node has a left child but no right child, you only need to consider the left subtree within parentheses immediately following the node's value. There's no need for parentheses for the nonexistent right child in this case.

  • If the node has both left and right children, you must include both in the string with their respective parentheses following the node's value.

Recursive calls are made to cover the entire tree, and at each step, you construct the string according to which children the current node has. By following these recursive rules, you ensure that you only include necessary parentheses, thus preventing any empty pairs from appearing in the final output string.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The solution uses a simple recursive algorithm, which is an application of the Depth-First Search (DFS) pattern. Here's how it works:

  • A helper function dfs is defined that accepts a node of the tree as its parameter. This function is responsible for the recursive traversal and string construction.

  • The base case of this recursion is when the dfs function encounters a None node. In binary trees, a None node signifies that you've reached beyond the leaf nodes (end of a branch). When this happens, an empty string is returned because there's nothing to add to the string representation from this node downwards.

  • When the current node is a leaf (neither left nor right child exists), we simply return the string representation of the node's value because leaves do not require parentheses according to the problem rules.

  • When a node has a left child but no right child, we include the left child's representation within parentheses following the node's value. However, the right side doesn't need any parentheses or representation because it's a None node.

  • The most involved case is when both left and right children exist. In this scenario, we need to represent both children. Therefore, recursively the dfs function is called for both the left and the right child, and their representations are enclosed in parentheses with the format: node value(left child representation)(right child representation). This ensures that the preorder traversal order is maintained.

Additionally, the given solution employs an inner function dfs and makes use of Python's string formatting to concatenate the values and parentheses cleanly.

Here's an implementation breakdown corresponding to the code sections:

1def tree2str(self, root: Optional[TreeNode]) -> str:
2    def dfs(root):
3        if root is None:  # Base case for NULL/None nodes.
4            return ''
5        if root.left is None and root.right is None:  # Leaf node case.
6            return str(root.val)
7        if root.right is None:  # Node with only left child case.
8            return f'{root.val}({dfs(root.left)})'
9        # Node with both left and right children case.
10        return f'{root.val}({dfs(root.left)})({dfs(root.right)})'
11
12    return dfs(root)  # Initial call to the dfs function with the [tree](/problems/tree_intro) root.
  • At the start, dfs(root) is called with the root of the binary tree.

  • The if conditions inside the dfs function handle the cases mentioned previously and are responsible for constructing the string as per the rules and format required by the problem statement.

  • The resulting string is built up step-by-step through recursive calls until the entire tree has been traversed, thus providing the correct string representation.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let’s consider a small binary tree example to illustrate the solution approach. The binary tree used in this example is as follows:

1     1
2    / \
3   2   3
4  / 
5 4 

In this tree:

  • The root node (1) has two children (2 and 3).
  • The left child of the root (2) has a left child of its own (4) and no right child.
  • The right child of the root (3) is a leaf node and has no children.
  • The leaf node (4) also has no children.

Using the problem's rules and solution approach, we perform a preorder traversal to construct the string:

  1. Start with the root (1). Since it's not None and not a leaf, the string representation starts with its value. So far we have the string "1".

  2. Next, visit the left child (2) of node (1). Again, as it is not a None or a leaf node and it has a left child but no right child, we include its left child wrapped in parentheses. So, we now have "1(2".

  3. We now go to the left child of node (2), which is node (4). This node is a leaf, so we simply return its value as a string, resulting in the substring "4". Adding this to the previous string, we get "1(2(4)".

  4. Since node (2) has no right child, we do not need to include it, and we close the parentheses for node (2). Our string is now "1(2(4))".

  5. Next, we consider the right child of the root, which is node (3). It is a leaf node, so we just need its value for the string, wrapped in parentheses because its sibling node (2) has children. Our string becomes "1(2(4))(3)".

  6. Finally, since we have represented both children of the root (1), we close the representation of the root. The final string is "1(2(4))(3)", with no unnecessary parentheses.

Using the given solution approach, the recursive function dfs would follow these steps internally to build the string representation smoothly. Here's the implementation of the tree structure in code and how the dfs function builds the string:

1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7def tree2str(root: Optional[TreeNode]) -> str:
8    def dfs(root):
9        if root is None:
10            return ''
11        if root.left is None and root.right is None:  # Leaf node case.
12            return str(root.val)
13        if root.right is None:  # Node with only left child case.
14            return f'{root.val}({dfs(root.left)})'
15        # Node with both left and right children case.
16        return f'{root.val}({dfs(root.left)})({dfs(root.right)})'
17
18    return dfs(root)
19
20# Example tree construction
21node4 = TreeNode(4)
22node2 = TreeNode(2, node4)
23node3 = TreeNode(3)
24root = TreeNode(1, node2, node3)
25# Call to transform tree into string
26print(tree2str(root))  # Output should be "1(2(4))(3)"

Following the recursive process described above using dfs, we obtain the expected string representation of the binary tree based on the problem’s guidelines.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def tree2str(self, root: TreeNode) -> str:
10        # Helper function to perform depth-first search traversal of the tree.
11        def dfs(node):
12            # If current node is None, return an empty string.
13            if node is None:
14                return ''
15          
16            # Convert the node's value to a string if it's a leaf node.
17            if node.left is None and node.right is None:
18                return str(node.val)
19          
20            # If the right child is None, only include the left child.
21            if node.right is None:
22                return f'{node.val}({dfs(node.left)})'
23          
24            # When both children are present, include both in the string representation.
25            return f'{node.val}({dfs(node.left)})({dfs(node.right)})'
26
27        # The main function call which starts the DFS traversal from the root.
28        return dfs(root)
29
1class Solution {
2
3    // Converts a binary tree into a string representation following specific rules:
4    // 1. Omit any children if both left and right child nodes are null
5    // 2. Include only left child if right child is null
6    // 3. Include both left and right children if they are not null
7    public String tree2str(TreeNode root) {
8        // Base case: if the current node is null, return an empty string
9        if (root == null) {
10            return "";
11        }
12      
13        // Case when both left and right child nodes are null
14        if (root.left == null && root.right == null) {
15            return Integer.toString(root.val);
16        }
17      
18        // Case when only the right child node is null
19        if (root.right == null) {
20            return root.val + "(" + tree2str(root.left) + ")";
21        }
22      
23        // Case when both child nodes are not null
24        // Note: The right child node is represented even when it might be null,
25        //       because the left child node is not null, and its existence must be acknowledged
26        return root.val + "(" + tree2str(root.left) + ")(" + tree2str(root.right) + ")";
27    }
28
29    // Definition for a binary tree node provided by the LeetCode environment
30    public class TreeNode {
31        int val;
32        TreeNode left;
33        TreeNode right;
34
35        TreeNode() {}
36
37        TreeNode(int val) {
38            this.val = val;
39        }
40
41        TreeNode(int val, TreeNode left, TreeNode right) {
42            this.val = val;
43            this.left = left;
44            this.right = right;
45        }
46    }
47}
48
1#include <string>  // Include the string library for string manipulation
2
3// Definition for a binary tree node.
4struct TreeNode {
5    int val;                     // Value of the node
6    TreeNode *left;              // Pointer to left child
7    TreeNode *right;             // Pointer to right child
8    // Constructors to initialize the node
9    TreeNode() : val(0), left(nullptr), right(nullptr) {}
10    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
11    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
12};
13
14class Solution {
15public:
16    // Function to convert a binary tree to a string representation.
17    std::string TreeToString(TreeNode* root) {
18        // Base case: if current node is nullptr, return an empty string
19        if (!root) return "";
20      
21        // Handle the case where the current node is a leaf node
22        if (!root->left && !root->right) {
23            return std::to_string(root->val);  // Simply return the string representation of the node value
24        }
25      
26        // Handle the case where the current node has a left child but no right child
27        if (!root->right) {
28            // Return the string representation of current node value and left subtree
29            return std::to_string(root->val) + "(" + TreeToString(root->left) + ")";
30        }
31      
32        // If current node has both left and right children
33        return std::to_string(root->val) + 
34               "(" + TreeToString(root->left) + ")" + 
35               "(" + TreeToString(root->right) + ")";
36    }
37};
38
1// Definition for a binary tree node.
2interface TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6}
7
8/**
9 * Serializes a binary tree to a string.
10 * @param {TreeNode | null} root - The root node of the binary tree.
11 * @returns {string} The serialized tree string, according to the LeetCode problem requirement.
12 */
13function tree2str(root: TreeNode | null): string {
14    // Return empty string for null nodes.
15    if (root == null) {
16        return '';
17    }
18  
19    // Return the value as a string if the node is a leaf.
20    if (root.left == null && root.right == null) {
21        return `${root.val}`;
22    }
23
24    // Serialize the left subtree. If left is null, use an empty string.
25    const leftStr = root.left ? `(${tree2str(root.left)})` : '()';
26  
27    // Serialize the right subtree only if it's not null.
28    const rightStr = root.right ? `(${tree2str(root.right)})` : '';
29
30    // Concatenate the string, omitting the right parenthesis if the right subtree is null.
31    return `${root.val}${leftStr}${rightStr}`;
32}
33

Time and Space Complexity

The time complexity of the given code is O(n), where n is the number of nodes in the binary tree. This is because the code performs a depth-first search (DFS) and visits each node exactly once when generating the string representation of the binary tree.

The space complexity of the code is also O(n) in the worst case when the tree is highly skewed (i.e., each node has only one child). This comes from the recursive call stack that could have a maximum depth equivalent to the number of nodes in the tree if the tree degenerates into a linked list. In a balanced tree, the space complexity would be O(log n) due to the height of the balanced tree being log n.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Depth first search is equivalent to which of the tree traversal order?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄