5
\$\begingroup\$

Write the shortest code that traverses a tree, depth-first.

Input

Any programmatical structure found in your language of choice: lists, tuples, queues etc.

Output

A list of "names" of the nodes in correct order as shown in Depth-first search article at Wikipedia.

Requirement:

A node should be able to contain an infinite number of child nodes.

Also, you're not required to actually print the result, just returning the correct result with the ability to use it in your program will do; I didn't really print mine below in my answer, the function simply returned a list.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ For programming languages supporting flattening infinite lists, this is basically a chameleon duplicate of the Make a list flat challenge. 🤷 \$\endgroup\$ Apr 26, 2023 at 15:01
  • 1
    \$\begingroup\$ What the hell, why there's already seven answers on my old post within the last 24 hours? What's going on? \$\endgroup\$
    – YasirA
    Apr 26, 2023 at 19:41
  • \$\begingroup\$ @KevinCruijssen Well, this post is a few years older than the post you linked, so technically the other post is a duplicate of this one, right? ;) \$\endgroup\$
    – YasirA
    Apr 26, 2023 at 19:41
  • 1
    \$\begingroup\$ Good point. ;) As for why there are more answers, that's pretty normal. When one person answers it, it'll go to the list of challenges on the home page as recently edited/answered, so more answers will see it and answer as well. :) \$\endgroup\$ Apr 26, 2023 at 20:30

12 Answers 12

3
\$\begingroup\$

Haskell — 70 characters

data N a=N{v::a,c::[N a]}
d n=f[n][]
f(x:y)=f(c x++y).(++[v x])
f _=id

In a more readable format:

data Node a = Node {value::a, children::[Node a]}

dfs :: Node a -> [a]
dfs node = dfs' [node] []
  where dfs' [] result = result
        dfs' (x:xs) result = dfs' (children x ++ xs) (result ++ [value x])

Sample tree:

sampleTree = 
    Node 1 [Node 2 [Node 3 [Node 4 [],
                            Node 5 []], 
                    Node 6 []],
            Node 7 [], 
            Node 8 [Node 9 [Node 10 [],
                            Node 11 []],
                    Node 12 []]]

Sample run:

*Main> dfs sampleTree
[1,2,3,4,5,6,7,8,9,10,11,12]
\$\endgroup\$
3
\$\begingroup\$

Haskell, 35 bytes

data D a=T[D a]a
d(T l n)=n:(d=<<l)

Try it online!

data D a=T[D a]a defines a labelled tree data structure. Constructor T takes a list of sub-trees and same value of an arbitrary type a (which however must be consistent throughout each tree).

Here is an example of a tree labelled with integers and the way this tree can be defined using the data structure:

   4
 / | \
1  5  2
  / \
 3   0

tree = T[T[]1, T[T[]3, T[]0]5, T[]2]4

The function d takes such a tree and returns a list of the tree's labels in depth-first order: Calling d tree yields [4,1,5,3,0,2].

\$\endgroup\$
3
\$\begingroup\$

Vyxal, 10 1, >2 or 8 bytes

Thanks to @Shaggy and @Kevin Cruijssen!!

If name of nodes are just a primitives (numbers, string) and 1D array is accepted output, than just:

f

If we need to do something with nodes, than:

fƛ<todo>

And if "A node should be able to contain an infinite number of child nodes":

ƛ:@[vx;f

Try it Online!

ƛ         # Start lambda map
 :        # Duplicate
  @       # Check is array or number (vectorized length==[] if a number)
   [      # Start If
    vx    # If array - vectorized recursive call of lambda
          # Else - do nothing (virtual "|" )
          # Close If (virtual "]" )
        ; # Close lambda 
        f # Flatten

\$\endgroup\$
3
  • 3
    \$\begingroup\$ I wonder if we're both overthinking this; would simply flattening the input not do the job? \$\endgroup\$
    – Shaggy
    Apr 26, 2023 at 14:41
  • \$\begingroup\$ @Shaggy OMG looks like this! But it is worth checking some test cases. If so it'll be funny! \$\endgroup\$
    – lesobrod
    Apr 26, 2023 at 14:46
  • 1
    \$\begingroup\$ @Shaggy I thought you were both aware of it, but didn't do so because of the 'infinite' requirement. 😅 Especially because this earlier 8-bytes Vyxal answer (the bottom one) ended with that same flatten f. \$\endgroup\$ Apr 26, 2023 at 15:28
2
\$\begingroup\$

Perl, 34

Perl 5.10 or later, run with perl -E'code here':

sub f{ref()?f($_):say for@{$_[0]}}

For example, running f [1,[2,[3,[4],[5]],[6]],[7],[8,[9,[10],[11]],[12]]] produces:

1
2
3
4
5
6
7
8
9
10
11
12
\$\endgroup\$
4
  • \$\begingroup\$ It's Perl 5.10 (and I should have put it in the answer as I usually do), you can either add -M5.010 to the command line, run as -E 'code here', or insert a use 5.010; header do the .pl file. \$\endgroup\$
    – J B
    Feb 6, 2011 at 15:24
  • \$\begingroup\$ @Yasir I read the comment (now), but do consider it more convenient to me to print the result instead of returning it. \$\endgroup\$
    – J B
    Feb 6, 2011 at 15:26
  • \$\begingroup\$ For older Perl, replace say with print"$_\n". Soooo longer. \$\endgroup\$
    – J B
    Feb 6, 2011 at 15:32
  • \$\begingroup\$ Yep, it works. I hurry voted your question twice. You may edit your answer to add notes about Perl version, or even shorter variant of your code in the future, so that I'll be able to vote up ;-) \$\endgroup\$
    – YasirA
    Feb 6, 2011 at 15:55
2
\$\begingroup\$

Japt, 1 byte

... It seems like simply flattening the array will to the job.

c

Try it

Japt, 10 bytes

cȶÔ?ßXÔ:X

Try it

cȶÔ?ßXÔ:X     :Implicit input of multi-dimensional array
c              :Flat map by
 È             :Passing each X through the following function
  ¶            :  Is strictly equal to
   Ô           :  Its reverse, if it's an array, or maximum, if it's an integer (see more detailed explanation below)
    ?          :  If true
     ß         :    Recursive call with argument
      XÔ       :    X reversed (because reversing an array in JS mutates the original)
        :X     :  Else return X

To (try to) explain how the Ô (which is a shortcut for the w method, without any arguments) allows us to differentiate between arrays & numbers by testing for strict equality:

While it's true that in JavaScript 2 arrays containing the exact same elements are not strictly equal as they are 2 distinct objects, an array assigned to a variable is, of course, equal to itself. Add to that that the reverse method for arrays (w in Japt) mutates the original array and that explains how an array assigned to a variable (X in this case) can be strictly equal to its reverse.

As to why a number does not equal its maximum, that's down to a peculiarity of Japt. Firstly, when applied to a number, Japt's w method returns the maximum of that number and the arguments passed to the method, as a Number. However, if no arguments are passed to the w method then the number it's applied to is returned as excpected but, for some reason, Japt converts the returned value to an Object and a Number cannot be strictly equal to an Object

\$\endgroup\$
1
\$\begingroup\$

PHP - 57 characters

<?function s($t){echo$t[0].'
';for(;$T=next($t);s($T));}

Test:

s(json_decode('[1,[2,[3,[4],[5]],[6]],[7],[8,[9,[10],[11]],[12]]]'));

Output:

1
2
3
4
5
6
7
8
9
10
11
12
\$\endgroup\$
1
\$\begingroup\$

Ruby - 37 35 31 25 characters

s=->t{p t.shift;t.map &s}

Test:

s[[1,[2,[3,[4],[5]],[6]],[7],[8,[9,[10],[11]],[12]]]]
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Save 1 by using 'map' instead of 'each' \$\endgroup\$
    – AShelly
    Feb 6, 2011 at 20:30
1
\$\begingroup\$

Scala, 125 bytes

Modified from @Laikoni's Haskell solution.


Golfed version. Try it online!

sealed trait D[A]
case class T[A](l:Seq[D[A]],v:A) extends D[A]
def d[A](t:D[A]):Seq[A]=t match{case T(l,v)=>v+:l.flatMap(d)}

Ungolfed version. Try it online!

object Main {
  sealed trait D[A]
  case class T[A](list: List[D[A]], value: A) extends D[A]

  def d[A](tree: D[A]): List[A] = tree match {
    case T(list, value) => value :: list.flatMap(d)
  }

  val t1 =
    T(
      List(
        T(List(), 1),
        T(
          List(
            T(List(), 3),
            T(List(), 0)
          ),
          5
        ),
        T(List(), 2)
      ),
      4
    )

  def main(args: Array[String]): Unit = {
    println(d(t1))
  }
}
\$\endgroup\$
1
\$\begingroup\$

JavaScript, 29 bytes

f=a=>a.flatMap(x=>1/x?x:f(x))

Attempt This Online!

\$\endgroup\$
1
  • \$\begingroup\$ Why not a=>a.flat(1/0)? \$\endgroup\$
    – InSync
    Apr 26, 2023 at 22:22
1
\$\begingroup\$

05AB1E, 2 (or 13) bytes

˜ε...

The ... indicates something you'd want to do with the item 'name' we're traversing depth-first over.

Try it online with a print statement to verify it's in the correct order, or verify some more test cases.
Try it online with a ragged list containing infinite sub-items.

Explanation:

˜   # Flatten the (implicit) ragged input-list
 ε  # Map over each item:
    #  (do something)

The main rule that stops most other programming languages from using a similar approach is "A node should be able to contain an infinite number of child nodes.". Fortunately, 05AB1E (build in Elixir) supports infinite lists and can flatten them without too much trouble, allowing this approach.

But for completeness sake, here is also a (13 bytes) program if this wouldn't have been possible:

"Ddi...ë®δ.V"©.V

The ... again indicates something you'd want to do with the item 'name' we're traversing depth-first over.
Assumes the 'names' of items used are positive integer ids.

Try it online with a print statement to verify it's in the correct order, or verify some more test cases.
Try it online with a ragged list containing infinite sub-items.

Explanation:

As always, 05AB1E is pretty bad at recursive functions over s, and will have to a use a string and evaluate to accomplish this..

"..."     # Push the recursive string explained below
     ©    # Store it in variable `®` (without popping)
      .V  # Evaluate and execute it as 05AB1E code,
          # using the (implicit) input as initial argument

D         # Duplicate the current value
 di       # Pop the copy, and if it's a (non-negative) integer:
   ...    #  (do something)
  ë       # Else (it's a list instead):
    δ     #  Map over the list:
   ® .V   #   Do a recursive call
\$\endgroup\$
1
  • \$\begingroup\$ Actually, I think based on what other submissions have done, just ˜ should be enough. \$\endgroup\$
    – noodle man
    Apr 26, 2023 at 19:20
0
\$\begingroup\$

Go, 89 bytes

import."fmt"
type N struct{v int;c[]N}
func f(n N){Println(n.v)
for _,c:=range n.c{f(c)}}

Attempt This Online!

This code also includes the type definition of a node N. Without it, the code is 63 bytes.

Prints node values to STDOUT, separated by newlines.

\$\endgroup\$
0
\$\begingroup\$

Python 3, 52 bytes

def f(t):
 yield t[0]
 for s in t[1]:yield from f(s)

Each node in the tree structure is encoded as a 2-tuple containing a value and an iterable of child nodes. The child nodes iterable may be infinite. Returns a generator containing values. Attempt This Online!

Explanation

def f(t):          # Define generator function f that takes tree t
 yield t[0]        # Yield the value of the root node
 for s in t[1]:    # For each subtree s:
  yield from f(s)  # Apply f to the subtree and yield each value in turn

Using itertools is never the answer.[citation needed] But in this case, it comes pretty close (57 bytes):

lambda t:chain(t[:1],*map(f,t[1]))
from itertools import*
\$\endgroup\$

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.