Deserializing binary trees depth-first is pretty easy, but doing it breadth-first is (hopefully) harder. Your mission, should you choose to accept it, is to do the latter.
The input will be a 1-D list of positive integers representing node values and some other consistent value representing the absence of a child (I'll use #
here). The first element of that list is the root of your tree, the next is the root's left child, then the root's right child, then the left child's left child, then the root's left child's right child, and so on. If a node doesn't have a left or right child, there will be a #
instead of a positive number to signify that.
You probably know how to do that already, but here's an example anyways:
Input: [1, 5, 3, #, 4, 10, 2]
First element is root
Tree List: [5, 3, #, 4, 10, 2]
1
Set the root's left child to the next element
Tree List: [3, #, 4, 10, 2]
1
/
5
Set the root's right child to the next element
Tree List: [#, 4, 10, 2]
1
/ \
5 3
That level's filled up, move on to 5's left child.
Since it's '#', there's no left child, so leave that empty.
Tree List: [4, 10, 2]
1
/ \
5 3
#
Set 5's right child to 4
Tree List: [10, 2]
1
/ \
5 3
# \
4
Move on to 3's left child
Tree List: [2]
1
/ \
5 3
# \ /
4 10
Move to 3's right child
Tree List: []
1
/ \
5 3
# \ / \
4 10 2
List is empty, so we're done.
Input
The input will be a 1-D list or multiple values read from STDIN. It won't be empty, and the first element will always be a positive integer. I used '#' here, but you can use null
, 0, or any consistent value that isn't a positive integer (please indicate what you use in your answer). The input may contain duplicate values and the tree it represents isn't necessarily sorted or in any sort of order.
Output
The output can be printed to STDOUT in the shape of a tree (you can make it look however you want as long as it's clear which nodes are connected to which and you don't just print the input back out), or returned from a function as a tree-like structure (the latter is preferred).
You can have each level on a separate line (or separated by some other character(s)), and each node also separated by some character(s) (like in Arnauld's JavaScript answer) OR you could have each child separated by some character, so long as it's clear which node is which node's child (like in Neil's Charcoal answer).
If your language doesn't have a "tree" data type or you can't make a Tree
class (or you just don't want to), you could also use a list to represent the tree. Just make sure that it's in an unambiguous format. For example, the tree above could be written as this:
[Value, Left Child, Right Child]
[1,
[5,
#, //No left child, so #
[4, #, #] //or just [4] since both children are absent
],
[3,
[10, #, #],
[2, #, #]
]
]
Test cases:
Input -> Output
Tree
[1] -> [1, #, #] //or [1], whatever you wish
Tree: 1 //or just 1
/ \
# #
([1, #, #] and [1, #] yield the same result as above)
[100, 4, #, 5, #, #] -> [100,[4,[5],#],#]
Tree: 100
/ \
4 #
/ \
5 #
/
#
[10, 5, 4, 2, #, 8, 1, 2, 2, 4] -> [10,[5,[2,[2],[2]],#],[4,[8,[4],#],[1]]]
Tree: 10
/ \
5 4
/ \ / \
2 # 8 1
/ \ /
2 2 4
[100, #, 4, 5, #, #] -> [100, #, [4, [5], #]]
Tree: 100
/ \
# 4
/ \
5 #
/ \
# #
Rules
- Since this is code-golf, shortest code (in bytes) wins.
100 point bounty for an answer that doesn't use any mutability whatsoever (but please don't just post something you found on StackOverflow).
[100, #, 4, 5, #, #]
. \$\endgroup\$[1, 5, 3, #, 4, 10, 2]
-> Output"1\n5 3\n# 4 10 2"
\$\endgroup\$"1\n5 3\n# 4 10 \n# # 2"
would, I think. See Arnauld's js answer \$\endgroup\$