algoadvance

Leetcode 606. Construct String from Binary Tree

Problem Statement

Given the root of a binary tree, construct a string consisting of parentheses and integers from a binary tree with the following rules:

1. Root node is always included in the string.
2. For each node, append the integer value of the node.
3. If the node has a left child, append an open parenthesis ‘(‘, the string constructed from the left child, and then a close parenthesis ‘)’.
4. If the node has a right child, and the node does not have a left child, you should still add an empty pair of parentheses ().
5. If the node has a right child, append an open parenthesis ‘(‘, the string constructed from the right child, and then a close parenthesis ‘)’.

Clarifying Questions

• Q: Are the values of each node in the binary tree unique?
  • A: Yes, for simplicity, we can assume that the values are unique.
• Q: Is it guaranteed that the input is a valid binary tree?
  • A: Yes, the input will always be a valid binary tree.
• Q: Can the tree be empty?
  • A: Yes, if the tree is empty, the output should be an empty string.

Strategy

1. Recursive Approach: I will use a recursive function to construct the string. The recursive function will:
   • Handle the base case when a node is NULL.
   • Append the node’s value to the resultant string.
   • Recursively call itself for the left child, and appropriately add parentheses.
   • Recursively call itself for the right child and handle the case where the left child is absent but the right child exists by adding empty parentheses for the left child.
2. Edge Cases:
   • An empty tree should return an empty string.
   • A tree with only root node should return just the root node’s value.

Code

Here is the C++ implementation for the problem:

#include <string>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    string tree2str(TreeNode* t) {
        if (!t) return "";
        return preorder(t);
    }
    
private:
    string preorder(TreeNode* node) {
        if (!node) return "";
        
        string result = to_string(node->val);
        
        if (node->left || node->right) {
            result += "(" + preorder(node->left) + ")";
        }
        
        if (node->right) {
            result += "(" + preorder(node->right) + ")";
        }
        
        return result;
    }
};

Time Complexity

• The time complexity of this solution is O(n), where n is the number of nodes in the binary tree. This is because the algorithm visits each node exactly once and performs a constant amount of work for each node.
• The space complexity is O(n) as well, considering the space needed for the recursion stack in the worst case, which happens when the binary tree is completely unbalanced.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?