Print a binary tree as aligned text
Company: Crusoe
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement a function that prints (or returns) an ASCII layout of a binary tree.
Requirements:
- Each node has a string value (assume it contains no spaces).
- If a node is missing a left or right child, print a placeholder `*` in that child position.
- The bottom row represents the leaf level of a *full* binary tree of height `h` (where `h` is the height of the input tree). It therefore has `2^(h-1)` leaf slots.
- Leaf slots must be separated by exactly one space.
- For every level above the leaves, each parent node must be positioned exactly in the middle (horizontally) between its left-child slot and right-child slot.
Return the output as a list of strings (one per level from top/root to bottom/leaves), or print it line by line.
Example (one possible formatting):
If the tree is:
- root = `A`
- A.left = `B`, A.right = `C`
- B.right = `D` (B.left is null)
Then the bottom level has 4 slots: `* D * *` (with single spaces), and parents are centered above their two children slots.
Explain any assumptions you make about node value width (e.g., single character vs variable-length strings).
Quick Answer: This question evaluates competence in binary tree data structures, spatial layout and string formatting by requiring conversion of a hierarchical tree into a constrained ASCII representation with placeholder handling for missing children; domain: Coding & Algorithms.
Render a binary tree as aligned ASCII text.
You are given the tree in **level-order** (breadth-first) as a list of single-character string values, where the sentinel `"#"` marks an absent node. For example `["A", "B", "C", "#", "D"]` is the tree with root `A`, children `B` (left) and `C` (right), and `B` having only a right child `D`.
Return the drawing as a **list of strings**, one per level from the root down to the leaves, obeying these rules:
- The picture is laid out as a **full** binary tree of height `h` (the height of the input tree). The bottom (leaf) row therefore has `2^(h-1)` slots.
- Each slot holds one character. A node that does not exist at a given position prints as `*`.
- In the bottom row the slots are separated by exactly one space (so the row is `2*2^(h-1) - 1` characters wide).
- For every level above the leaves, each parent is placed exactly in the middle (horizontally) between its left-child slot and its right-child slot. Padding to the left of a node's column is spaces.
**Assumption:** node values are single characters with no spaces, so every slot is one column wide. (For variable-length values you would widen each slot to the longest value and center within it; that is out of scope here.)
**Example** — input `["A", "B", "C", "#", "D"]` (height 3) returns:
```
A
B C
* D * *
```
Constraints
- 1 <= number of input entries; level_order[0] != "#" for a non-empty tree.
- Each present value is a single character with no spaces; "#" is reserved as the absent-node sentinel.
- Input list is in level-order (BFS) and only includes positions down to the deepest present node.
- Tree height h satisfies 2^(h-1) leaf slots fitting in memory (h is small in practice).
Examples
Input: ["A", "B", "C", "#", "D"]
Expected Output: [" A ", " B C ", "* D * *"]
Explanation: The prompt example. Height 3 -> 4 leaf slots. B has only a right child D, so its left leaf slot is '*'. C is missing both children -> '* *'. Parents B and C are centered above their child pairs, and A is centered above the whole row.
Input: ["A"]
Expected Output: ["A"]
Explanation: Single-node tree: height 1, one leaf slot, one line containing just the root.
Hints
- First rebuild the tree from the level-order array (skip a child when its value is "#"), then compute the height h.
- The bottom row is a full level with 2^(h-1) leaf slots; slot i sits at column 2*i, so the line is 2*2^(h-1) - 1 characters wide.
- Recurse positionally over a FULL tree: a node covering leaf slots [lo, hi] is drawn at the midpoint column (2*lo + 2*hi)/2; split into [lo, mid] and [mid+1, hi] for its children. Print '*' wherever the real node is missing.