-4
$\begingroup$

I am looking for a suggestion. I know it is possible to construct a binary tree from an array. I want to know that vice verse is true? Is it possible to construct an array from a binary tree? If yes how could I construct it? Any well known algorithm for that? I am looking for suitable datastructure in Java.

Thank you in advance..

$\endgroup$
2
$\begingroup$

Yes, of course. Just put all vertices in the tree into an array, in any order as you like.

There are different popular methods, that all generate interesting properties:

  • Pre-order: do a DFS starting at the root, and store the vertices in the same order as you visit them.

    This has the advantage, that all nodes of a subtree are next to each other. Which means that you can handle subtree queries (e.g. what is the minimum of the subtree at vertex $v$?) with the same methods as range queries (what is the minimum in a subarray?)

  • In-oder: Recursively put all vertices of the left in the array, then the vertex itself, and then recursively ll vertices of the right.

    If your binary tree was in fact a binary search tree, then this will fill the array in ascending order.

  • Post-order: First left vertices, then right vertices and then the vertex itself.

    Don't know any usefulness for this one, but these three tree traversals are usually taught in any beginner programming course together, as they are very similar.

  • Breath-first traversal: Do a BFS starting at the root, and fill the array in the visit order.

    This will leave all vertices of the same depth next to each other.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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