algoadvance

Leetcode 655. Print Binary Tree

Problem Statement

(Directly from Leetcode)

You need to print the binary tree in a 2-D array in reverse order. Here are the steps to do that:

1. The row number r should be equal to the height of the tree.
2. The number of columns c should be equal to 2^h - 1 - where h is the height of the tree.
3. Assign the root of the tree at the center of the top row (index 0).
4. For each node nd at position (r, c), you should assign its left child to the position (r+1, c - 2^(h-r-1)) and the right child to (r+1, c + 2^(h-r-1)).
5. A null node should be represented by an empty string.

Clarifying Questions

1. Should the output array be filled with empty strings where there are no nodes?
   • Yes, the output 2-D array should have empty strings "" for null nodes.
2. Can the tree have duplicate values?
   • Yes, the tree can have duplicate values.
3. Should the input tree always be non-empty?
   • Yes, it’s guaranteed that the tree is non-empty.

Strategy

1. Calculate Tree Height:
   • Use a recursive helper function to determine the height of the tree.
2. Initialize Result Array:
   • Create a 2-D array filled with empty strings (""), having the specified dimensions.
3. Recursive Placement:
   • Use a helper function to recursively place each node at the correct position in the 2-D array.

Step-by-Step Approach:

1. Calculate the height of the binary tree.
2. Initialize a 2-D array result of dimensions h x (2^h - 1) filled with empty strings.
3. Recursively place the nodes in their respective positions in the array, adjusting column indices based on the tree depth.

Code

#include <vector>
#include <string>
#include <cmath>
#include <algorithm>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int getHeight(TreeNode* root) {
        if (!root) return 0;
        return 1 + std::max(getHeight(root->left), getHeight(root->right));
    }
    
    void fill(TreeNode* root, std::vector<std::vector<std::string>>& res, int r, int c, int height) {
        if (!root) return;
        res[r][c] = std::to_string(root->val);
        // Calculate midpoint offset for the next level
        int offset = std::pow(2, height - r - 1);
        if (root->left) fill(root->left, res, r + 1, c - offset, height);
        if (root->right) fill(root->right, res, r + 1, c + offset, height);
    }

    std::vector<std::vector<std::string>> printTree(TreeNode* root) {
        int height = getHeight(root);
        int width = std::pow(2, height) - 1;
        std::vector<std::vector<std::string>> res(height, std::vector<std::string>(width, ""));
        fill(root, res, 0, (width - 1) / 2, height);
        return res;
    }
};

Time Complexity

• Height Calculation: O(N), where N is the number of nodes in the tree (in the worst case, we visit each node once).
• Filling the 2-D Array: O(N), as we also visit each node exactly once to place it in the correct position.

Thus, the overall time complexity is O(N).

Space Complexity

• The 2-D array has dimensions of h x (2^h - 1), where h is the height of the tree.
• The recursion depth will be h.

Thus, the overall space complexity is O(h * 2^h), which simplifies to O(N) in terms of tree nodes if we consider a complete binary tree structure.

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?