6
\$\begingroup\$

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 , 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).

\$\endgroup\$
  • \$\begingroup\$ Sandbox. I didn't get any replies for 4 days, so I'm posting it here \$\endgroup\$ – user Sep 29 at 14:11
  • 1
    \$\begingroup\$ I'd suggest to add a test case where a node near the root has no left child, such as [100, #, 4, 5, #, #]. \$\endgroup\$ – Arnauld Sep 29 at 15:09
  • \$\begingroup\$ @Arnauld Yup, added one. May I ask why you suggested that? (I want to make sure I've put everything in the rules instead of in the test cases) \$\endgroup\$ – user Sep 29 at 15:17
  • 1
    \$\begingroup\$ @user It's not a problem in the spec, but I believe that some buggy implementations may fail when an upper left node is missing and work on the other test cases. \$\endgroup\$ – Arnauld Sep 29 at 15:19
  • \$\begingroup\$ "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)" is very vague. Is this allowed? Input [1, 5, 3, #, 4, 10, 2] -> Output "1\n5 3\n# 4 10 2" \$\endgroup\$ – Stef Sep 29 at 23:38
5
\$\begingroup\$

JavaScript (ES10),  81  80 bytes

Saved 1 byte thanks to @Shaggy

Expects -1 for a non-existing child node. Returns a string where each line contains all the nodes at this depth.

a=>(g=r=>a+a&&(r=r.map(x=>+x||a.shift()||-1))+`
`+g(r.flatMap(x=>[x=-!~x,x])))``

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Do you need the 0 on the initial call to g? \$\endgroup\$ – Shaggy Sep 29 at 18:31
  • \$\begingroup\$ @Shaggy Nope. :-) Thank you. \$\endgroup\$ – Arnauld Sep 29 at 18:45
  • 1
    \$\begingroup\$ Nice (ab)use of using backticks to call a function :) \$\endgroup\$ – Shaggy Sep 29 at 18:46
3
\$\begingroup\$

Charcoal, 40 bytes

≔⟦S⟧θ⊞υθ≔⁰ηWS«F¬⁼#ι«≔⟦ι⟧ι⊞υι»⊞§υ⊘ηι≦⊕η»θ

Try it online! Link is to verbose version of code. Takes input on separate lines with newline termination and empty nodes marked with # and output uses Charcoal's default output for a nested array structure which is basically preorder traversal with blank lines to show movement back up the tree. Explanation:

≔⟦S⟧θ

Create a node for the root.

⊞υθ

Add the node to the list of all nodes.

≔⁰η

Start counting the inputs.

WS«

Repeat until the blank line marking the end of the input list.

F¬⁼#ι«

If this value is not the empty node marker, then...

≔⟦ι⟧ι

... turn it into a node, and...

⊞υι

... add it to the list of all nodes.

»⊞§υ⊘ηι

Push the node or marker to the child currently being filled.

≦⊕η

Increment the input count. The child being filled is half (rounded down) of the input count.

»θ

Output the finished tree.

| improve this answer | |
\$\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.