algoadvance

The problem “606. Construct String from Binary Tree” on LeetCode is defined as follows:

You need to construct a string from a binary tree with the preorder traversal way. The preorder traversal follows visit node -> traverse left -> traverse right.

You might use parentheses to indicate subtrees. Empty parentheses () are unnecessary, and you should omit them when you understand that it doesn’t affect the tree’s structure.

Example:

Input: Binary tree: [1,2,3,4]
       1
     /   \
    2     3
   /     
  4     
Output: "1(2(4))(3)"

Input: Binary tree: [1,2,3,null,4]
       1
     /   \
    2     3
     \  
      4 
Output: "1(2()(4))(3)"

Clarifying Questions

  1. What type of data will be present in the tree nodes? The tree nodes will contain integer values.

  2. Can the tree be empty? Yes, the tree can be empty, in which case the output should be an empty string.

  3. Are there any constraints on the size of the tree? There’s no explicit size constraint provided, but typically, we’ll assume it fits in memory for solving typical interview-level problems.

Strategy

  1. Recursive Traversal: We’ll perform a preorder traversal (visit the root, traverse the left subtree, and then traverse the right subtree).

  2. String Construction:

    • Append the value of the current node to the string.
    • If the left subtree is not empty, recursively process the left subtree and enclose the result in parentheses.
    • If the left subtree is empty but the right subtree is not, add () for the left subtree.
    • If the right subtree is not empty, recursively process the right subtree and enclose the result in parentheses.

Code

# 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: TreeNode) -> str:
        # Helper function to recurse through the tree and build the string
        def dfs(node: TreeNode) -> str:
            if not node:
                return ""
            
            # Convert the node value to string
            result = str(node.val)
            
            # Process the left child
            if node.left or node.right:  # if there's a right child we need parentheses
                result += f"({dfs(node.left)})"
            
            # Process the right child
            if node.right:
                result += f"({dfs(node.right)})"
            
            return result
        
        return dfs(root)

# Example Usage:
# Construct the tree [1,2,3,null,4]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(4)

sol = Solution()
print(sol.tree2str(root))  # Output: "1(2()(4))(3)"

Time Complexity

The time complexity for this solution is (O(n)), where (n) is the number of nodes in the tree. Each node is visited exactly once in a preorder traversal, and building the string for each node requires constant time operations for appending strings.

The space complexity is (O(h)) where (h) is the height of the tree. This accounts for the recursive stack space used during the preorder traversal.

Try our interview co-pilot at AlgoAdvance.com