Paths and hierarchical namespaces

coreCommon atStripeAnthropicGoogleMetaRead firstStacksHash mapsPractise in the Sandbox →

A path is a list of names joined by /. Normalizing it is a stack walk: push ordinary names, pop on .., skip . and empty names, and never pop past the root. Storing a hierarchy (files, config keys, S3-style prefixes, org charts) is a tree of maps: each directory maps child name to child, so a lookup costs O(depth), not O(total entries).

The idea in plain words

Think of giving directions in a building: “go into wing A, then room 3, then back out one room, then into room 5”. You keep a mental list of where you are. Going in adds to the list. Going back out removes the last entry. Standing still (“stay here”, which is .) changes nothing. And if you’re already outside the building, “back out” leaves you outside.

That mental list is a stack. The path string is just the instructions.

The other half is storage. A file system is not a flat list of strings like "/home/ana/todo.txt". It’s nested folders, each of which knows only its direct children. Model it the same way: a directory is a hash map from name to child, a file is a leaf. To find /home/ana/todo.txt, look up home in the root, then ana in that, then todo.txt. Three O(1) lookups, regardless of how many files exist elsewhere.

Words to have ready:

Term	Meaning
Absolute path	Starts with /: measured from the root.
Relative path	Measured from the current directory (cwd).
Canonical path	One spelling per location: leading /, single separators, no . or .., no trailing slash.
Lexical (textual) normalization	Rewriting the string without looking at the file system.
Resolution	Asking the file system, which follows symbolic links. Can give a different answer.

See it

Edit the current directory and the path. Watch each name either push, pop, or get skipped. Try a path with more .. than names, a trailing slash, ... (an ordinary name), or an absolute path that discards cwd.

Normalize a path with a stack

step through

current dir (absolute)path

names in the path, split on "/"

..

notes

∅

.

2024

..

..

.config

∅

012345678

stack (bottom = closest to root)

home

ana

projects

result/home/ana/projects

depth3

pushed a namepopped by ".."skipped ("" or ".")".." at rootconsumed

The path is relative, so start from the current directory's names: [home, ana, projects]. An empty path would stop here.

↺◀▶ Play▶1 / 11

And the storage side: a path lookup walks one map per name. Try a missing name, and a path that goes through a file.

Walk a tree of maps

step through

canonical path

try /home/ana/todo.txt/x, /home/carl, /tmp

at/

keys here{etc, home, tmp}

statuswalk

walked throughcurrent nodefoundmissing / not a directory

Start at the root map. Each directory is a hash map from child name to child, so each step is one O(1) lookup.

↺◀▶ Play▶1 / 6

When to reach for it

The problem says…	What fits
“simplify / canonicalize this path”, “cd semantics”	A stack of names. Split, then push/pop/skip.
“create nested directories”, “list a directory”, “total size under a folder”	A tree of maps: lookups walk the path; aggregates are a DFS over a subtree.
“find all keys starting with /config/db/”	A tree (or trie) by segment, or a sorted map with a range scan on the prefix.
“user-supplied file name, serve it from this folder”	Resolve, then a boundary-aware containment check. Security, not string tidying.
“rename / move a subtree”	Tree of maps: detach one entry, attach it elsewhere. O(depth), not O(size of subtree).

How it works

Normalizing (the mechanics)

1. Pick a starting stack: empty if the path starts with /, otherwise the names of the current directory.
2. Split the path on /. You get empty strings for // and trailing slashes; keep that in mind.
3. For each name: skip "" and "."; on ".." pop if the stack isn’t empty (the root’s parent is the root); otherwise push the name.
4. Join: "/" + "/".join(stack). An empty stack gives "/".

Only exactly . and .. are special. ..., .hidden and x.. are ordinary names. That one sentence catches a lot of off-by-one string checks like name.startswith(".").

Textual vs physical '..'

Textual normalization assumes a/b/.. is a. On a real disk, if b is a symbolic link to /x/y, then a/b/.. is physically /x. That’s why pathlib.PurePosixPath keeps .. as written, and why cd -L and cd -P exist in POSIX shells. Ask which meaning the problem wants.

Use the standard library, but know its quirks

In production you rarely hand-roll this. You do need to know what the stdlib actually does:

Call	Result	Note
Python posixpath.normpath("//a")	"//a"	POSIX lets exactly two leading slashes mean something special, so Python keeps them. Three collapse to one.
Python posixpath.normpath("a/../..")	".."	Relative paths can keep leading ...
Python posixpath.normpath("")	"."	Empty means “here”.
Python os.path.join("/a", "/b")	"/b"	An absolute second part throws away the first.
Node path.posix.normalize("/a/b/")	"/a/b/"	Keeps the trailing slash. normalize("//a") is "/a".
Node path.posix.join("/a", "/b")	"/a/b"	Unlike Python, join doesn’t reset on an absolute part. path.posix.resolve("/a", "/b") does: "/b".
.NET Path.Combine("/a", "/b")	"/b"	Like Python. Path.GetFullPath collapses ./.. and follows the host OS rules (drive letters and \ on Windows).

None of these lexical functions touch the disk, so none of them follow symlinks. For that you need os.path.realpath / Path.resolve(), fs.realpathSync, or .NET’s FileSystemInfo.ResolveLinkTarget.

Building block: “is this path inside that folder?”

The classic security use. A user asks for ../../etc/passwd. You must decide whether the resolved target is still inside your base folder. The trap is comparing strings: /srv/app2/secret starts with /srv/app. Compare on a name boundary.

1. Canonicalize the base folder.
2. Join the user’s path to it and let the stdlib collapse . and ... An absolute user path replaces the base.
3. Inside means: equal to the base, or starting with the base plus a separator.

Python

is_inside.py

import posixpath


def naive_inside(base: str, user_path: str) -> bool:
    # BUG: plain string prefix. "/srv/app2" starts with "/srv/app".
    return posixpath.normpath(posixpath.join(base, user_path)).startswith(base)


def is_inside(base: str, user_path: str) -> bool:
    """True if base/user_path stays within base (textually; see realpath note)."""
    base = posixpath.normpath(base)                    # 1. canonical base, no trailing "/"
    # 2. join, then let the stdlib collapse "." and "..". An absolute
    #    user_path replaces base entirely, and then fails the check below.
    target = posixpath.normpath(posixpath.join(base, user_path))
    # 3. compare on a name boundary: equal, or base followed by "/"
    return target == base or target.startswith(base.rstrip("/") + "/")
    # In production, use os.path.realpath on both sides first so a symlink
    # inside base that points outside it is caught too.


if __name__ == "__main__":
    base = "/srv/app"
    assert is_inside(base, "uploads/a.png")
    assert is_inside(base, ".")
    assert is_inside(base, "a/../../app/x")            # wanders out and back in
    assert not is_inside(base, "../app2/secret")
    assert naive_inside(base, "../app2/secret")        # the boundary bug
    assert not is_inside(base, "/etc/passwd")          # absolute input escapes
    assert not is_inside(base, "../../etc/passwd")
    print("ok")

TypeScript

is_inside.ts

import assert from "node:assert/strict";
import path from "node:path";

const P = path.posix; // fix the flavour so results don't depend on the OS

export function naiveInside(base: string, userPath: string): boolean {
  // BUG: plain string prefix. "/srv/app2" starts with "/srv/app".
  return P.resolve(base, userPath).startsWith(base);
}

/** True if base/userPath stays within base (textually; see realpath note). */
export function isInside(base: string, userPath: string): boolean {
  const root = P.resolve(base); // 1. canonical base, no trailing "/"
  // 2. resolve collapses "." and ".."; an absolute userPath replaces base.
  const target = P.resolve(root, userPath);
  // 3. compare on a name boundary: equal, or base followed by "/"
  return target === root || target.startsWith(root === "/" ? "/" : root + "/");
  // In production, fs.realpathSync both sides first to catch symlinks.
}

const base = "/srv/app";
assert.equal(isInside(base, "uploads/a.png"), true);
assert.equal(isInside(base, "."), true);
assert.equal(isInside(base, "a/../../app/x"), true); // wanders out and back in
assert.equal(isInside(base, "../app2/secret"), false);
assert.equal(naiveInside(base, "../app2/secret"), true); // the boundary bug
assert.equal(isInside(base, "/etc/passwd"), false); // absolute input escapes
assert.equal(isInside(base, "../../etc/passwd"), false);
console.log("ok");

C#

is_inside.cs

// Path.GetFullPath follows the host OS rules: "/" on Linux/macOS, "\" and drive
// letters on Windows. This demo assumes a Unix-style host.
static bool NaiveInside(string baseDir, string userPath) =>
    // BUG: plain string prefix. "/srv/app2" starts with "/srv/app".
    Path.GetFullPath(Path.Combine(baseDir, userPath)).StartsWith(baseDir, StringComparison.Ordinal);

// True if baseDir/userPath stays within baseDir (textually; see realpath note).
static bool IsInside(string baseDir, string userPath)
{
    string root = Path.TrimEndingDirectorySeparator(Path.GetFullPath(baseDir)); // 1. canonical base
    // 2. Combine drops root when userPath is absolute; GetFullPath collapses "." and "..".
    string target = Path.GetFullPath(Path.Combine(root, userPath));
    // 3. compare on a name boundary. Ordinal: case rules are a file-system question.
    string prefix = root.EndsWith(Path.DirectorySeparatorChar) ? root : root + Path.DirectorySeparatorChar;
    return target == root || target.StartsWith(prefix, StringComparison.Ordinal);
    // In production, resolve symlinks too (FileSystemInfo.ResolveLinkTarget).
}

const string Base = "/srv/app";
if (!IsInside(Base, "uploads/a.png")) throw new Exception("plain child");
if (!IsInside(Base, ".")) throw new Exception("the base itself");
if (!IsInside(Base, "a/../../app/x")) throw new Exception("out and back in");
if (IsInside(Base, "../app2/secret")) throw new Exception("sibling with shared prefix");
if (!NaiveInside(Base, "../app2/secret")) throw new Exception("naive should show the bug");
if (IsInside(Base, "/etc/passwd")) throw new Exception("absolute escapes");
if (IsInside(Base, "../../etc/passwd")) throw new Exception("dot-dot escapes");
Console.WriteLine("ok");

Building block: walking a tree of maps

Once a hierarchy lives in nested maps, most reports are a DFS that carries the path down with it. Sort children at each level if output order matters, because hash maps don’t promise one.

Python

file_paths / render.py

# A directory is a dict of name -> child; a file is its content (a str).
Tree = dict[str, "Tree | str"]


def file_paths(node: Tree, prefix: str = "") -> list[str]:
    """Every file's full path, depth-first, children in sorted order."""
    out: list[str] = []
    for name in sorted(node):                      # 1. sorted -> deterministic output
        child = node[name]
        full = f"{prefix}/{name}"                  # 2. build the path on the way down
        if isinstance(child, dict):
            out.extend(file_paths(child, full))    # 3. recurse into directories
        else:
            out.append(full)                       # 4. leaves are files
    return out


def render(node: Tree, indent: str = "") -> list[str]:
    """A `tree`-style drawing: the last child gets a corner, others a tee."""
    lines: list[str] = []
    names = sorted(node)
    for i, name in enumerate(names):
        last = i == len(names) - 1
        child = node[name]
        lines.append(indent + ("└── " if last else "├── ") + name + ("/" if isinstance(child, dict) else ""))
        if isinstance(child, dict):                # the pipe continues only under non-last
            lines.extend(render(child, indent + ("    " if last else "│   ")))
    return lines


if __name__ == "__main__":
    fs: Tree = {"src": {"main.py": "print()", "util": {"io.py": ""}}, "README": "hi", "docs": {}}
    assert file_paths(fs) == ["/README", "/src/main.py", "/src/util/io.py"]
    assert render(fs) == ["├── README", "├── docs/", "└── src/", "    ├── main.py", "    └── util/", "        └── io.py"]
    assert file_paths({}) == []
    print("ok")

TypeScript

file_paths / render.ts

import assert from "node:assert/strict";

// A directory is an object of name -> child; a file is its content (a string).
type Node = string | Dir;
interface Dir { [name: string]: Node }

const byCodepoint = (a: string, b: string) => (a < b ? -1 : a > b ? 1 : 0);

/** Every file's full path, depth-first, children in sorted order. */
export function filePaths(node: Dir, prefix = ""): string[] {
  const out: string[] = [];
  for (const name of Object.keys(node).sort(byCodepoint)) { // 1. deterministic order
    const child = node[name];
    const full = `${prefix}/${name}`; // 2. build the path on the way down
    if (typeof child === "string") out.push(full); // 4. leaves are files
    else out.push(...filePaths(child, full)); // 3. recurse into directories
  }
  return out;
}

/** A `tree`-style drawing: the last child gets a corner, others a tee. */
export function render(node: Dir, indent = ""): string[] {
  const names = Object.keys(node).sort(byCodepoint);
  return names.flatMap((name, i) => {
    const last = i === names.length - 1;
    const child = node[name];
    const isDir = typeof child !== "string";
    const line = indent + (last ? "└── " : "├── ") + name + (isDir ? "/" : "");
    return isDir ? [line, ...render(child, indent + (last ? "    " : "│   "))] : [line];
  });
}

const fs: Dir = { src: { "main.py": "print()", util: { "io.py": "" } }, README: "hi", docs: {} };
assert.deepEqual(filePaths(fs), ["/README", "/src/main.py", "/src/util/io.py"]);
assert.deepEqual(render(fs), ["├── README", "├── docs/", "└── src/", "    ├── main.py", "    └── util/", "        └── io.py"]);
assert.deepEqual(filePaths({}), []);
console.log("ok");

C#

file_paths / render.cs

// A directory is a Dictionary of name -> child; a file is its content (a string).
var fs = new Dictionary<string, object>
{
    ["src"] = new Dictionary<string, object>
    {
        ["main.py"] = "print()",
        ["util"] = new Dictionary<string, object> { ["io.py"] = "" },
    },
    ["README"] = "hi",
    ["docs"] = new Dictionary<string, object>(),
};

var paths = Tree.FilePaths(fs, "");
if (string.Join(",", paths) != "/README,/src/main.py,/src/util/io.py") throw new Exception(string.Join(",", paths));
var lines = Tree.Render(fs, "");
string[] want = ["├── README", "├── docs/", "└── src/", "    ├── main.py", "    └── util/", "        └── io.py"];
if (!lines.SequenceEqual(want)) throw new Exception(string.Join("\n", lines));
Console.WriteLine("ok");

static class Tree
{
    // Every file's full path, depth-first, children in sorted (ordinal) order.
    public static List<string> FilePaths(Dictionary<string, object> node, string prefix)
    {
        var outList = new List<string>();
        foreach (var name in node.Keys.Order(StringComparer.Ordinal)) // 1. deterministic order
        {
            string full = $"{prefix}/{name}";                          // 2. path on the way down
            if (node[name] is Dictionary<string, object> dir) outList.AddRange(FilePaths(dir, full)); // 3.
            else outList.Add(full);                                    // 4. leaves are files
        }
        return outList;
    }

    // A `tree`-style drawing: the last child gets a corner, others a tee.
    public static List<string> Render(Dictionary<string, object> node, string indent)
    {
        var lines = new List<string>();
        var names = node.Keys.Order(StringComparer.Ordinal).ToList();
        for (int i = 0; i < names.Count; i++)
        {
            bool last = i == names.Count - 1;
            var dir = node[names[i]] as Dictionary<string, object>;
            lines.Add(indent + (last ? "└── " : "├── ") + names[i] + (dir is null ? "" : "/"));
            if (dir is not null) lines.AddRange(Render(dir, indent + (last ? "    " : "│   ")));
        }
        return lines;
    }
}

What it costs

Let L be the length of the path string, d its depth (number of names), N the total entries in the tree, and k the entries in one directory.

Operation	Cost	Why
Normalize a path	O(L)	Each name is split once and pushed or popped at most once.
Look up a path in a tree of maps	O(d) average	One hash lookup per name. Independent of N.
Same lookup in a flat dict[full_path]	O(L) to hash, O(1) lookup	Fast for exact hits, but “list this directory” or “delete this subtree” becomes O(N) scans.
List one directory, sorted	O(k log k)	Read its map’s keys, then sort.
Aggregate a subtree (sizes, counts)	O(subtree size)	DFS visits every entry below. Cache totals per directory if it’s hot, and update them along the path on writes (O(d) per write).
Move/rename a subtree	O(d)	Re-link one map entry. A flat map would rewrite every key under it.

Variations you’ll meet

• Key-value namespaces. Object stores (S3 keys like logs/2024/05/01.gz), etcd/ZooKeeper nodes, feature-flag keys checkout.v2.enabled. Same shape, different separator.
• Symbolic links. A name whose value is another path. Resolution has to restart from the target, and must detect loops (POSIX returns ELOOP after a bounded number of hops).
• Trailing-slash meaning. Some tools treat dir/ as “must be a directory” (rsync even changes behaviour). Decide whether it’s ignored.
• Case sensitivity. Linux file systems are case-sensitive; default macOS (APFS) and Windows (NTFS) are case-insensitive but case-preserving. README and readme may be one file or two.
• Windows paths. Drive letters, \, UNC paths \\server\share, reserved names like CON. Use the platform library.
• Glob matching. *.py, **/test_*. Match name by name against pattern segments; ** matches zero or more segments.

Pitfalls

• split("/") produces empty strings. "/a//b/".split("/") is ["", "a", "", "b", ""]. Skip them, or you’ll push empty names.
• Popping past the root. stack.pop() on an empty list throws in Python and returns undefined in JS. Guard it.
• Prefix checks without a boundary. "/srv/app2".startswith("/srv/app").
• Treating .foo as special. Only . and .. are.
• Forgetting the root case when joining: an empty stack must print "/", not "".
• A file in the middle of a path. /notes.txt/x must fail cleanly, not crash because a string has no children.
• Removing what contains you. Deleting the current directory, or one of its ancestors, leaves cwd dangling. Decide the rule.
• Unsorted listings. Hash map iteration order isn’t a spec. Sort when the output is compared.

In the interview

• Ask: absolute or relative? Is there a current directory? What does .. at the root do? Are ... and .hidden ordinary names? Trailing slashes? Are there symlinks, and is .. textual or physical?
• Ask whether the file system is real or simulated. “No directory needs to exist” changes everything.
• Say the representation choice out loud: “I’ll store a tree of maps, so lookup is O(depth) and moving a subtree is one re-link. A flat map of full paths would make listing and subtree deletes O(N).”
• State the invariant for normalization: “The stack always holds the canonical names from the root to where I am.”
• Expect follow-ups: mkdir -p, recursive delete, subtree sizes, a current directory, symlinks and loop detection, permissions per directory.

Check yourself

Check yourself

pick one

cwd is /a/b. What is the canonical result of cd '../../../c/./d/'?

A/c/dB/a/c/dC../c/dDerror: above root

Check yourself

pick one

You serve files from /srv/app and check `resolved.startswith('/srv/app')`. Which request slips through?

A/srv/app/../app/xB../app-backup/db.sqliteCimg/logo.pngD./index.html

Check yourself

pick one

Directories are stored as nested hash maps. Which operation is NOT O(depth)?

ARead one file by pathBRename a directoryCTotal size of everything under a directoryDCheck whether a path exists

Practice on your own

Classic exercises, not gym questions:

• Given a list of file paths, group the duplicates by file content (paths as keys, content as values).
• Print a nested JSON object as dotted keys (db.host, db.port) and back.
• Implement glob matching with * and ? for a single name, then ** across segments.
• Given a flat list of (employee, manager) pairs, build the org tree and print it tree-style.

Go deeper

• Python os.path and pathlib: normpath, realpath, and why PurePath keeps ...
• Node.js path: normalize, join, resolve, relative, and the posix/win32 variants.
• .NET file path formats: how Windows paths normalize, and how Path.GetFullPath behaves.
• POSIX, Pathname resolution and the cd utility: the -L/-P rules for ...
• OWASP: Path Traversal.

Related

StacksThe structure behind path normalization.

TriesTrees keyed by segment, for prefix queries.

Depth-first searchSubtree totals, listings and deletes.

Parsing and tokenizingSplitting input into tokens without losing edge cases.