Print a binary tree as aligned text
Problem: Print a Binary Tree as Aligned Text
Implement a function that generates an ASCII layout of a given binary tree. The output should represent the tree structure with specific horizontal alignment rules.
Requirements
- Each node in the tree has a string value. Assume these values contain no spaces.
- If a node is missing a left or right child, a placeholder
*character must be printed in that child's position. - The bottom-most row of the output must correspond to the leaf level of a full binary tree of height
h, wherehis the height of the input tree. This implies2^(h-1)leaf slots. - All leaf slots on the bottom row must be separated by exactly one space.
- For every level above the leaves, each parent node must be positioned horizontally exactly in the middle between its left-child slot and right-child slot.
Output Format
The function should return the output as a list of strings, where each string represents one level of the tree from top (root) to bottom (leaves). Alternatively, it can print the output line by line.
Example
Consider the following tree structure:
- Root node:
A A's left child:BA's right child:CB's left child:nullB's right child:D
A possible formatted output for this tree would have 4 slots on the bottom level: * D * * (with single spaces between slots). Parent nodes like A and B would be centered above their respective child slots.
Clarification Point
The candidate is expected to explain any assumptions made regarding the width of node string values (e.g., whether they are always single characters or can be variable-length strings).
AI interview prep
Core dilemma
The central engineering conflict is accurately calculating and maintaining precise horizontal alignment for nodes at each level, especially when dealing with variable-width node values and the requirement for parent nodes to be perfectly centered between their children's *slots*, not just the children themselves, within a fixed-width grid derived from a full binary tree's leaf count. This requires a careful balance of recursive structure traversal and spatial layout algorithms.
2 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Print a binary tree as aligned text
Problem: Print a Binary Tree as Aligned Text
Implement a function that generates an ASCII layout of a given binary tree. The output should represent the tree structure with specific horizontal alignment rules.
Requirements
- Each node in the tree has a string value. Assume these values contain no spaces.
- If a node is missing a left or right child, a placeholder
*character must be printed in that child's position. - The bottom-most row of the output must correspond to the leaf level of a full binary tree of height
h, wherehis the height of the input tree. This implies2^(h-1)leaf slots. - All leaf slots on the bottom row must be separated by exactly one space.
- For every level above the leaves, each parent node must be positioned horizontally exactly in the middle between its left-child slot and right-child slot.
Output Format
The function should return the output as a list of strings, where each string represents one level of the tree from top (root) to bottom (leaves). Alternatively, it can print the output line by line.
Example
Consider the following tree structure:
- Root node:
A A's left child:BA's right child:CB's left child:nullB's right child:D
A possible formatted output for this tree would have 4 slots on the bottom level: * D * * (with single spaces between slots). Parent nodes like A and B would be centered above their respective child slots.
Clarification Point
The candidate is expected to explain any assumptions made regarding the width of node string values (e.g., whether they are always single characters or can be variable-length strings).