1
$\begingroup$

Wondering if there is a way to convert a binary tree into a grid such as this:

                    a
                  /   \
                 b     c
                / \   / \
               d   e f   g


                    or


                 d--b--e
                    |
                    a
                    |
                 f--c--g


                    to


                 d--b--e
                 |  |  |
                 y--a--x
                 |  |  |
                 f--c--g

An arbitrary sized binary tree. I'm not super familiar with binary tree properties so I am not sure if this would even be possible or if edge cases would prevent it from being possible.

$\endgroup$
3
  • 2
    $\begingroup$ Can you explain in more detail what you mean by "convert a binary tree into a grid"? In particular, do you want each edge in the binary tree to correspond to an edge of the grid? $\endgroup$ Apr 22, 2018 at 6:30
  • $\begingroup$ I am not sure exactly, it starts to get confusing right then lol! It seems you'd have to test out large binary trees to get a sense for their shape, and then see what kinds of grids they can fit into and the patterns of connectivity. But that seems brittle, so I'm wondering if there is a more robust approach. $\endgroup$
    – Lance
    Apr 22, 2018 at 6:35
  • 1
    $\begingroup$ If you don't have a question, what kind of answer do you expect? $\endgroup$ Apr 22, 2018 at 6:35

1 Answer 1

2
$\begingroup$

A vertex in the grid has $O(d)$ vertices at distance $d$ from it. In contrast, the complete binary tree of height $h$ as $2^h$ vertices at distance $h$ from the root. Therefore there is no isometric embedding of arbitrary binary trees in the grid. Similar considerations show that there is also no embedding of bounded distortion (in which distances increase by at most a constant factor).

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.