How can only directories be listed, that do not have another child directory?

Imagine a structure like /A /A/AA /A/AB /A/AB/ABB /B /C /C/CC /C/CC/CCC /C/CC/CCC/CCCC I would like to use find to list only /A/AA /A/AB/ABB /B /C/CC/CCC/CCCC.

The starting point would be find . -type d, but neither -mindepth nor -maxdepth can be used, can -noleaf help (I could not get it to react the way I wanted it to)?


Here's a POSIX-compliant solution that postprocesses the output of find to remove directories that have a listed subdirectory. It assumes that there are no newlines in the directory names.

{ find . -type d; echo; } |
awk 'index($0,prev"/")!=1 && NR!=1 {print prev}
     1 {sub(/\/$/,""); prev=$0}'

Explanation: the awk script delays the printing of each line until it's read the next line and only prints the previous line if it's not a prefix. This takes advantage of the fact that find lists subdirectories immediately after their parent. The extra "/" is to avoid spuriously removing foo when foobar also exists. The inelegant NR!=1 avoids printing an initial empty line, and the inelegant echo; is not to have an equally inelegant special case for the last line. The call to sub removes a trailing slash from the toplevel directory, in case e.g. find ./ was called.

As usual there's a cryptic zsh one-liner.

echo **/.(e\''test -z $REPLY/*(/DN[1])'\':h)

Longer, more readable version:

is_leaf () { [ -z $REPLY/*(/DN[1]) ] }
echo **/.(+is_leaf:h)

The last line can be simplified to echo **/(+is_leaf) if you dont' mind the trailing /.

Summary explanation: The stuff in parentheses are glob qualifiers, documented in the zshexpn man page. We filter the results of the glob **/ (expanding to the current directory and all its subdirectories), keeping only those for which the function is_leaf (or the code between '…') returns 0. The filter code globs the subdirectories of the match being tested ($REPLY) (in fact, [1] makes it stops after the first subdirectory) and returns a status indicating whether at least one subdirectory was found. The glob qualifier / restricts the expansion to directories; N means the expansion is empty if there is no match; D causes dot files to be included; :h is a history modifier and causes the /. suffix to be stripped (in general it means dirname).

Just to illustrate the possibilities of zsh's glob qualifiers, here are two other variants (longer and I think more obscure) with a corresponding is_leaf function:

echo **/.(e\''tmp=($REPLY/*(/DN[1])); ((!#tmp))'\':h)
echo **/.(e\''$REPLY/*(/DN[1]e:REPLY=false:)'\':h)
is_leaf () { set -- $REPLY/*(/DN[1]); ((!#)); }
is_leaf () { return $REPLY/*(/DN[1]e:REPLY=1:) }
  • It looks like I should start working with zsh... Anyway, I think the awk script more readable than the sed script. But the whole find/awk breaks, if a path different from "." is specified for find. In this case, the path name would be repeated as a first output if there exist any leafes below that path. Example: mkdir -p A/AA; { find A/ -type d; echo; } | awk 'index($0,prev"/")!=1 && NR!=1 {print prev} 1 {prev=$0}' will output A/ as well as A/AA. I could not test the zsh yet... – MaoPU Oct 6 '10 at 13:05
  • @MaoPU: the problem in your example is the trailing /; the code would have worked with find A or find /A. I've fixed my answer. There's still a very uncommon edge case that's not right (if you run the code in a filesystem with no directory other than the root, you get an empty line instead of a line with /). Change the awk print statement accordingly if you care about this bug. I've also found a slightly simpler zsh version (it's almost readable now). – Gilles 'SO- stop being evil' Oct 6 '10 at 18:29
  • Great explanation. I found out, that bash-4.x also supports ** globbing, so there might be a way to write one of those neat one liners in bash, too. Since the original question suggested the usage of find and the awk script is fairly readable, I went basically for this solution and added leaf () { { find -- "${1:-.}" -type d; echo; } | awk 'index($0,prev"/")!=1 && NR!=1 {print prev} 1 {sub(/\/$/,""); prev=$0}'; } to my .bashrc. Thank you. – MaoPU Oct 6 '10 at 19:21
  • @MaoPU: bash 4 has **, so you don't need find, but you still need some other way of filtering out the non-leaf directories. You can use a for loop over **/., but it's not really one-liner material. – Gilles 'SO- stop being evil' Oct 6 '10 at 19:43

This is what I use:

leaf () { find "${1:-.}" -depth -type d | sed  'h; :b; $b; N; /^\(.*\)\/.*\n\1$/ { g; bb }; $ {x; b}; P; D'; }

Call it using the directory to start from:

leaf /start/dir
  • I couldn't not upvote a sed script that uses the other operators (than s), especially since the hold space is particularly appropriate here. (Note that the semicolon isn't POSIX and may have to be replaced by newlines outside Linux.) But I couldn't upvote an unquoted variable substitution! (And there's still the problem of an argument whose name begins with -, which is a general find annoyance.) – Gilles 'SO- stop being evil' Oct 5 '10 at 22:56
  • @Gilles: What is the problem of other operators than s (just joking, right?) Just to understand this: What is the problem of an unquoted variable substitution? None of my test cases broke the script. Anyway, is there a solution for the names starting with - (don't see a general find solution to this in your answer neither)? – MaoPU Oct 6 '10 at 12:54
  • @MaoPU: For names starting with - (such as a directory called -print), I think if you have a single path and believe in the implementer scrupulously following a 21st-century version of POSIX, then find -- "${1:-.}" is good enough. Otherwise you can preprocess the argument to prepend ./ if it starts with -. – Gilles 'SO- stop being evil' Oct 6 '10 at 18:34
  • @MaoPU: For why the quotes are needed, try with a directory called * (without quotes, the shell would expand the pattern) or foo bar (without quotes, the shell would split the argument into words). – Gilles 'SO- stop being evil' Oct 6 '10 at 18:35
  • @Gilles: Yes, in general in know this, but in this case I could not reproduce an error with a path containting white space. Also I was trying to experiment with the find -- to stop it from reading arguments, but it would not work. I think, to make it bullet proof, you need to test for relative or absolute paths and prepend a ./ in case it is a relative path. – MaoPU Oct 6 '10 at 19:17

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.